Finding a most biased coin with fewest flips
Event details
| Date | 25.07.2014 |
| Hour | 15:00 › 16:00 |
| Speaker | Karthik Chandrasekaran, Harvard |
| Location | |
| Category | Conferences - Seminars |
Abstract: The multi-armed bandit problem is a well-studied problem with applications in bioinformatics, clinical trials, etc. A variation of the problem is to find the most rewarding arm in the fewest possible number of steps. When the rewards are Bernoulli, this is equivalent to the problem of finding the most biased coin among a set of coins by tossing them adaptively. The goal here is to devise a strategy that minimizes the expected number of tosses until there exists a coin whose posterior probability of being most biased is at least 1-delta, for a given delta. In this talk, I will present an optimal adaptive strategy for a particular probabilistic setting of the problem. I will
show that the strategy performs the best possible action in each step by employing tools from the field of Markov games.
Based on joint work with Richard Karp.
Bio: Karthik Chandrasekaran is a Simons postdoctoral research fellow at Harvard University. He obtained his B. Tech. in Computer Science and Engineering from the Indian Institute of Technology, Madras and his Ph.D. in Algorithms, Combinatorics, and Optimization from Georgia Tech. His primary research interests are in optimization, integer programming, probabilistic methods and analysis, and randomized algorithms. He will be joining as an assistant professor in the University of Illinois at Urbana-Champaign in Oct, 2014.
show that the strategy performs the best possible action in each step by employing tools from the field of Markov games.
Based on joint work with Richard Karp.
Bio: Karthik Chandrasekaran is a Simons postdoctoral research fellow at Harvard University. He obtained his B. Tech. in Computer Science and Engineering from the Indian Institute of Technology, Madras and his Ph.D. in Algorithms, Combinatorics, and Optimization from Georgia Tech. His primary research interests are in optimization, integer programming, probabilistic methods and analysis, and randomized algorithms. He will be joining as an assistant professor in the University of Illinois at Urbana-Champaign in Oct, 2014.
Practical information
- Informed public
- Free
Organizer
- Nisheeth Vishnoi