Skip to content. | Skip to navigation

Personal tools

Theme for TIFR Centre For Applicable Mathematics, Bangalore


You are here: Home / Events / Partition identification using multi-armed bandits

Partition identification using multi-armed bandits

Prof. Sandeep K Juneja STCS, TIFR
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

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.

Filed under: