Problems in Pure Exploration Multi-Armed Bandits with Multi-Dimensional Feedback and Criteria

Many applications can be modeled as follows: an agent is given access to several distributions and she wishes to determine those that meet some pre-specified criteria by sampling from the distributions in a sequential experiment. For example internet companies often perform A/B/n testing, which consists of determining which of several website design options is the best (e.g., maximizes the probability of a purchase) by diverting traffic to each of the options. As another example, in crowdsourcing, it is important to identify high-quality workers from a large pool of workers, e.g., those who give the correct answer with the highest probability on a random question. It is common practice to use "gold standard" questions, i.e., questions whose answers are known, to assess the quality of a worker. In these applications, it is of interest to determine the answer as quickly as possible so as to save money from experimentation. Pure exploration multi-armed bandits provide a framework for designing statistically efficient adaptive algorithms for solving these problems. Most of the literature has focused on settings where at each round of the sequential experiment the feedback is scalar-valued (i.e., one random number is observed). In this thesis, I argue that many applications exhibit multi-dimensional feedback and criteria. For example, in the crowdsourcing application, it is natural to require that a worker give the correct answer with high probability and at a suitable pace (e.g., within 15 seconds) and when a prospective crowdsourcing worker answers a gold standard question, there is feedback both on whether a worker is correct and her response time. To study and solve applications of this multi-dimensional nature, I introduce novel pure exploration multi-armed bandit problems and design new algorithms that enjoy both strong theoretical guarantees and excellent empirical performance.PhDElectrical and Computer EngineeringUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttps://deepblue.lib.umich.edu/bitstream/2027.42/151539/1/jkatzsam_1.pd