BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1148
DTSTAMP:20230914T125952Z
SUMMARY:Regret minimization in heavy-tailed bandits.
DESCRIPTION:Speaker: Shubhada Agrawal\n\nAbstract: \nIn this talk\, we will
revisit the classical regret-minimization problem in the multi-armed band
it setting. This problem has been well studied when the arm distributions
are restricted to have either bounded support or belong to a single parame
ter exponential family (distributions characterized by 1 parameter\, for e
xample\, Gaussian with fixed variance\, Bernoulli distributions\, Poisson
distributions\, etc.). However\, in many applications\, the underlying ar
m distributions fail to satisfy these simplifying assumptions. We will con
sider a much general class of arm distributions and work with a weaker ass
umption that the moments of order $(1 + \\epsilon)$ are uniformly bounded
by a known constant B\, for some given $\\epsilon > 0$. We will look at an
optimal algorithm that matches the lower bound exactly in the in the firs
t-order term.\n\nRegret-minimization algorithms typically rely on construc
ting tight confidence intervals for means of the underlying distributions.
We will also look at new anytime-valid confidence intervals for means\, w
hich are based on the empirical likelihood principle. Algorithms using the
MGF-based concentration of the empirical mean for bounded support distrib
utions (Auer et al.\, 2002)\, or of the robust estimators for mean\, like
the truncated empirical mean in the case of heavy-tailed distributions (Bu
beck et al.\, 2013)\, exist in the literature. We will see exactly where t
he framework of the optimal algorithm gains over these existing algorithms
that use MGF-based confidence intervals for the mean.\n\nIf time permits\
, we will also look at a mixture-martingale-based proof for the validity o
f the proposed confidence intervals.\n\nThis talk is based on joint work w
ith Sandeep Juneja and Wouter M. Koolen (the paper can be found here). I w
ill not assume any prerequisites beyond a basic understanding of probabili
ty theory.\n\nZoom link: https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlp
ZWmhNYTJGQTF6Zz09\n
URL:https://www.tcs.tifr.res.in/web/events/1148
DTSTART;TZID=Asia/Kolkata:20210806T171500
DTEND;TZID=Asia/Kolkata:20210806T181500
END:VEVENT
END:VCALENDAR