Partition identification using multi-armed 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 \delta-correct algorithm (algorithm that restricts wrong identification probability to a pre-specified \delta) must satisfy. Further, we propose \delta-correct algorithms that for small \delta can match these bounds.