Sign inSign up
Finding a most biased coin with fewest flips thumbnail
Pause
Mute
Subtitles
Playback speed
0.25
0.5
0.75
1
1.25
1.5
1.75
2
Full screen

Finding a most biased coin with fewest flips

Published on Jul 15, 20142183 Views

Karthekeyan Chandrasekaran

We study the problem of learning a most biased coin among a set of coins by tossing the coins adaptively. The goal is to minimize the number of tosses until we identify a coin whose posterior probabil

COLT 2014 - Barcelona

Related categories

Computational Learning TheoryOn-line LearningStatistical LearningSupervised LearningUnsupervised Learning

Chapter list

Finding a most biased coin with fewest flips00:00
The Coin-Toss Problem00:00
Related work01:09
A Decision-Theoretic Perspective02:20
Problem Setting03:29
Results05:04
The Strategy05:44
Likelihood Ratio05:48
Algorithm06:46
Correctness Probability07:59
Optimality08:30
An alternate view of the algorithm - 108:41
An alternate view of the algorithm - 210:46
Multi-token Markov Game - 111:30
Multi-token Markov Game - 211:34
Optimal Strategy [DTW ´03]13:05
Optimality for our Markov Game13:50
Open Questions14:47