Partition identification using multiarmed bandits
Speaker 
Prof. Sandeep K Juneja
STCS, TIFR


When 
Jun 13, 2019
from 11:00 AM to 12:00 PM 
Where  LH 006 
Add event to calendar 
vCal iCal 
Abstract: Given a vector of unknown probability distributions, or arms, each of which can be sampled independently, we consider the problem of identifying the partition to which this vector belongs from a finitely partitioned universe of such vector of distributions. We primarily consider partitions where the vector of means of arms lie either in a given set or its complement in a Euclidean space. The sets considered correspond to half spaces or where either the set or its complement is a polytope, or more generally, a convex set. In these settings, exploiting the problem geometry, we characterize the lower bounds on mean number of samples from each arm that any \deltacorrect algorithm (algorithm that restricts wrong identification probability to a prespecified \delta) must satisfy. Further, we propose \deltacorrect algorithms that for small \delta can match these bounds.