BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
BEGIN:VEVENT
UID:123@lincs.fr
DTSTART;TZID=Europe/Paris:20141105T140000
DTEND;TZID=Europe/Paris:20141105T150000
DTSTAMP:20170313T171219Z
URL:https://www.lincs.fr/events/unimodal-bandits-without-smoothness/
SUMMARY:Unimodal Bandits without Smoothness
DESCRIPTION:\n\n\n Abstract:\nIn this talk we present new results on the
 stochastic bandit problems with a continuum set of arms and where the
 expected reward is a continuous and unimodal function of the arm. Our
 setting for instance includes the problem considered in (Cope\, 2009) and
 (Yu\, 2011). No assumption beyond unimodality is made regarding the
 smoothness and the structure of the expected reward function. Our first
 result is an impossiblity result: without knowledge of the smoothness of
 the reward function\, there exists no stochastic equivalent to Kiefer's
 golden section search (Kiefer\, 1953). Further\, we propose Stochastic
 Pentachotomy (SP)\, an algorithm for which we derive finite-time regret
 upper bounds. In particular\, we show that\, for any expected reward
 function $mu$ that behaves as $mu(x)=mu(x^star)-C|x-x^star|^xi$ locally
 around its maximizer $x^star$ for some $xi\, C&gt\;0$\, the SP algorithm is
 order-optimal\, i.e.\, its regret scales as $O(sqrtTlog(T))$ when the time
 horizon $T$ grows large. This regret scaling is achieved without the
 knowledge of $xi$ and $C$. Our algorithm is based on asymptotically optimal
 sequential statistical tests used to successively prune an interval that
 contains the best arm with high probability. To our knowledge\, the SP
 algorithm constitutes the first sequential arm selection rule that achieves
 a regret scaling as $O(sqrtT)$ up to a logarithmic factor for non-smooth
 expected reward functions\, as well as for smooth functions with unknown
 smoothness. This is a joint work with Alexandre Proutière available at :
 http://arxiv.org/abs/1406.7447\n\n\nBiography:\nBio: Richard Combes
 received the Engineering degree from Telecom ParisTech (2008)\, the
 Master's degree in mathematics from university of Paris VII (2009) and the
 Ph.D. degree in mathematics from university of Paris VI (2012). He was a
 visiting scientist in INRIA (2012) and a post-doc in KTH (2013). He is
 currently an Assistant Professor in Supélec. He received the best paper
 award at CNSM 2011. His current research interests include communication
 networks\, stochastic systems and their control and machine
 learning.\n\n\n\n&nbsp\;
CATEGORIES:Seminars,Youtube
LOCATION:LINCS Meeting Room 40\, 23\, avenue d'Italie\, Paris\, 75013\,
 France
GEO:48.8283983;2.3568972000000485
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=23\, avenue d'Italie\,
 Paris\, 75013\, France;X-APPLE-RADIUS=100;X-TITLE=LINCS Meeting Room
 40:geo:48.8283983,2.3568972000000485
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:STANDARD
DTSTART:20141026T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
END:VTIMEZONE
END:VCALENDAR