Finding a most biased coin with fewest flips

Karthekeyan Chandrasekaran, Richard Karp
Proceedings of The 27th Conference on Learning Theory, PMLR 35:394-407, 2014.

Abstract

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 probability of being most biased is at least 1-δfor a given δ. Under a particular probabilistic model, we give an optimal algorithm, i.e., an algorithm that minimizes the expected number of future tosses. The problem is closely related to finding the best arm in the multi-armed bandit problem using adaptive strategies. Our algorithm employs an optimal adaptive strategy—a strategy that performs the best possible action at each step after observing the outcomes of all previous coin tosses. Consequently, our algorithm is also optimal for any given starting history of outcomes. To our knowledge, this is the first algorithm that employs an optimal adaptive strategy under a Bayesian setting for this problem. Our proof of optimality employs mathematical tools from the area of Markov games.

Cite this Paper

BibTeX
@InProceedings{pmlr-v35-chandrasekaran14, title = {Finding a most biased coin with fewest flips}, author = {Chandrasekaran, Karthekeyan and Karp, Richard}, booktitle = {Proceedings of The 27th Conference on Learning Theory}, pages = {394--407}, year = {2014}, editor = {Balcan, Maria Florina and Feldman, Vitaly and Szepesvári, Csaba}, volume = {35}, series = {Proceedings of Machine Learning Research}, address = {Barcelona, Spain}, month = {13--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v35/chandrasekaran14.pdf}, url = {https://proceedings.mlr.press/v35/chandrasekaran14.html}, abstract = {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 probability of being most biased is at least 1-δfor a given δ. Under a particular probabilistic model, we give an optimal algorithm, i.e., an algorithm that minimizes the expected number of future tosses. The problem is closely related to finding the best arm in the multi-armed bandit problem using adaptive strategies. Our algorithm employs an optimal adaptive strategy—a strategy that performs the best possible action at each step after observing the outcomes of all previous coin tosses. Consequently, our algorithm is also optimal for any given starting history of outcomes. To our knowledge, this is the first algorithm that employs an optimal adaptive strategy under a Bayesian setting for this problem. Our proof of optimality employs mathematical tools from the area of Markov games.} }
Endnote
%0 Conference Paper %T Finding a most biased coin with fewest flips %A Karthekeyan Chandrasekaran %A Richard Karp %B Proceedings of The 27th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2014 %E Maria Florina Balcan %E Vitaly Feldman %E Csaba Szepesvári %F pmlr-v35-chandrasekaran14 %I PMLR %P 394--407 %U https://proceedings.mlr.press/v35/chandrasekaran14.html %V 35 %X 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 probability of being most biased is at least 1-δfor a given δ. Under a particular probabilistic model, we give an optimal algorithm, i.e., an algorithm that minimizes the expected number of future tosses. The problem is closely related to finding the best arm in the multi-armed bandit problem using adaptive strategies. Our algorithm employs an optimal adaptive strategy—a strategy that performs the best possible action at each step after observing the outcomes of all previous coin tosses. Consequently, our algorithm is also optimal for any given starting history of outcomes. To our knowledge, this is the first algorithm that employs an optimal adaptive strategy under a Bayesian setting for this problem. Our proof of optimality employs mathematical tools from the area of Markov games.
RIS
TY - CPAPER TI - Finding a most biased coin with fewest flips AU - Karthekeyan Chandrasekaran AU - Richard Karp BT - Proceedings of The 27th Conference on Learning Theory DA - 2014/05/29 ED - Maria Florina Balcan ED - Vitaly Feldman ED - Csaba Szepesvári ID - pmlr-v35-chandrasekaran14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 35 SP - 394 EP - 407 L1 - http://proceedings.mlr.press/v35/chandrasekaran14.pdf UR - https://proceedings.mlr.press/v35/chandrasekaran14.html AB - 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 probability of being most biased is at least 1-δfor a given δ. Under a particular probabilistic model, we give an optimal algorithm, i.e., an algorithm that minimizes the expected number of future tosses. The problem is closely related to finding the best arm in the multi-armed bandit problem using adaptive strategies. Our algorithm employs an optimal adaptive strategy—a strategy that performs the best possible action at each step after observing the outcomes of all previous coin tosses. Consequently, our algorithm is also optimal for any given starting history of outcomes. To our knowledge, this is the first algorithm that employs an optimal adaptive strategy under a Bayesian setting for this problem. Our proof of optimality employs mathematical tools from the area of Markov games. ER -
APA
Chandrasekaran, K. & Karp, R.. (2014). Finding a most biased coin with fewest flips. Proceedings of The 27th Conference on Learning Theory, in Proceedings of Machine Learning Research 35:394-407 Available from https://proceedings.mlr.press/v35/chandrasekaran14.html.

Related Material