13
$\begingroup$

Imagine the following setup: You have 2 coins, coin A which is guaranteed to be fair, and coin B which may or may not be fair. You are asked to do 100 coin flips, and your objective is to maximize the number of heads.

Your prior information about coin B is that it was flipped 3 times and yielded 1 head. If your decision rule was simply based on comparing the expected probability of heads of the 2 coins, you would flip coin A 100 times and be done with it. This is true even when using reasonable Bayesian estimations (posterior means) of the probabilities, since you have no reason to believe that coin B yields more heads.

However, what if coin B is actually biased in favor of heads? Surely the "potential heads" you give up by flipping coin B a couple of times (and therefore gaining information about its statistical properties) would be valuable in some sense and therefore would factor into your decision. How can this "value of information" be described mathematically?

Question: How do you construct an optimal decision rule mathematically in this scenario?

$\endgroup$
  • $\begingroup$ I'm deleting my answer. Too many people are complaining that I explicitly used a prior (which is standard in the literature). Enjoy Cam Davidson Pilon's incorrect answer where he also assumes a prior (but no one objects) and claims as optimal a method which is 1.035 below optimal. $\endgroup$ – Douglas Zare Mar 15 '13 at 21:53
  • $\begingroup$ whoah, when did this all happen? BTW, I would agree with Douglas that using a prior is fine. I retract my optimality assertion, as well. $\endgroup$ – Cam.Davidson.Pilon Mar 15 '13 at 22:02
  • $\begingroup$ I'm accepting Cam's solution because it helped me a lot. I agree that it's not optimal, but unless somebody can point out a general optimal solution which can easily be computed, it's the best bet. $\endgroup$ – M. Cypher Mar 15 '13 at 22:04
  • $\begingroup$ Why was it so bad that I used a prior (which I clearly stated) to answer a question tagged "bayesian?" $\endgroup$ – Douglas Zare Mar 15 '13 at 22:06
  • 1
    $\begingroup$ I didn't criticize the use of a prior. I mentioned as a sidenote that there might be more appropriate priors than the uniform one (e.g. Jeffrey's), but this is only marginally relevant to the question. Your solution was perfectly fine, just not as useful to me since it doesn't generalize easily. $\endgroup$ – M. Cypher Mar 15 '13 at 22:10
7
$\begingroup$

Multi-armed Bandit

This is a particular case of a Multi-Armed bandit problem. I say a particular case because generally we don't know any of the probabilities of heads (in this case we know one of the coins has probability 0.5).

The issue you raise is known as the exploration vs exploitation dilemma: do you explore the other options, or do you stick with what you think is the best. There is an immediate optimal solution assuming you knew all probabilities: simply choose the coin with the highest probability of winning. The problem, as you have alluded to, is that we are unsure about what the true probabilities are.

There is lots of literature on the subject, and there are many deterministic algorithms, but since you tagged this Bayesian, I'd like to tell you about my personal favourite solution: the Bayesian Bandit!

The Baysian Bandit Solution

The Bayesian approach to this problem is very natural. We are interested in answering "What is the probability that coin X is the better of the two?".

A priori, assuming we have observed no coin flips yet, we have no idea what the probability of coin B's Heads might be, denote this unknown $p_B$. So we should assign a prior uniform distribution to this unknown probability. Alternatively, our prior (and posterior) for coin A is trivially concentrated entirely at 1/2.

As you have stated, we observe 2 tails and 1 heads from coin B, we need to update our posterior distribution. Assuming a uniform prior, and flips are Bernoulli coin-flips, our posterior is a $Beta( 1 + 1, 1 + 2)$. Comparing the posterior distributions or A and B now:

enter image description here

Finding an approximately optimal strategy

Now that we have the posteriors, what to do? We are interested in answering "What is the probability coin B is the better of the two" (Remember from our Bayesian perspective, although there is a definite answer to which one is better, we can only speak in probabilities):

$$w_B = P( p_b > 0.5 )$$

The approximately optimal solution is to choose B with probability $w_B$ and A with probability $1 - w_B$. This scheme maximizes out expected gains. $w_B$ can be computed in calculated numerically, as we know the posterior distribution, but an interesting way is the following:

1. Sample P_B from the posterior of coin B
2. If P_B > 0.5, choose coin B, else choose coin A.

This scheme is also self-updating. When we observe the outcome of choosing coin B, we update our posterior with this new information, and select again. This way, if coin B is really bad we will choose it less, and it coin B is in fact really good, we will choose it more often. Of course, we are Bayesians, hence we can never be absolutely sure coin B is better. Choosing probabilistically like this is the most natural solution to the exploration-exploitation dilemma.

This is a particular example of Thompson Sampling. More information, and cool applications to online advertising, can be found in Google's research paper and Yahoo's research paper. I love this stuff!

$\endgroup$
  • 2
    $\begingroup$ I don't think that strategy is correct. I don't think you should be choosing whether to pick A or B probabilistically. $\endgroup$ – Douglas Zare Mar 15 '13 at 14:24
  • 2
    $\begingroup$ I don't think that paper says what you think it does. If you disagree, please compute the expected number of heads you will obtain under that strategy. $\endgroup$ – Douglas Zare Mar 15 '13 at 15:12
  • 4
    $\begingroup$ I don't think this is close to optimal. It suggests that on the first flip, you chose B with probability 1/2. It should be clear that you get no information if you choose A, so you should choose B all of the time. The amount you lose by this error is about 0.12 when you make it, so it costs you about 0.06 on the first step. You lose a similar amount when you roughly flip a coin to decide whether to collect any information on the next few steps. Flipping A early means you have less time to exploit an advantage you might find. $\endgroup$ – Douglas Zare Mar 15 '13 at 15:24
  • 2
    $\begingroup$ Another way to see that this probabilistic method is not optimal is to consider the last flip. You should not sample from the distribution for B to decide whether to flip B on the last toss, you should compare the mean value with $0.5$. $\endgroup$ – Douglas Zare Mar 15 '13 at 15:28
  • 1
    $\begingroup$ @DouglasZare If your only measure is the expected number of heads, given our coin flips, then the best strategy is to always pick coin A. But this is incomplete as it focuses too much on the explioitation, and not enough on the potential upside of exploration. The logical conclusion of your suggestion is, if we restart the experiment, to flip coin B once: if it is Tails, always choose A; else flip it again, if it is Heads always choose B. $\endgroup$ – Cam.Davidson.Pilon Mar 15 '13 at 15:28
8
$\begingroup$

This is a simple case of a multi-armed bandit problem. As you note, you want to balance the information you collect by trying the unknown coin when you think is suboptimal in the short run against exploiting the knowledge you have.

In the classical multi-armed bandit problem, you would not be certain of the probability for either coin. However, here you are given that you know the value of coin A, so when you flip A, you get no information. In fact, you might as well ignore the stochastic nature of A, and assume you get a flat $1/2$ per choice of A. This means if it is ever right to flip coin A, then you should keep flipping A. So, you just want to find the optimal stopping rule for when you should give up on B. This depends on the prior distribution for the parameter for B and the number of trials. With a greater number of trials, exploring has more value, so you would test B more.

In general, I think you can't get away from a dynamic programming problem, although there might be special cases where the optimal strategy can be found and checked more simply.

With a uniform prior, here is where you should stop:

$(0 ~ \text{heads}, 3 ~\text{tails}), (1 ~\text{head}, 5 ~\text{tails}), (2 ~\text{heads}, 6 ~\text{tails}), (3,7), (4,8),...(31,35), (32,35), (33,36), (34,37), ... (41,44), (42,44), ... (46,48), (47,48), (48,49), (49,50)$.

Under this strategy, you expect to collect $61.3299$ heads.

I used the following Mathematica code to compute the equities:

Clear[Equity];
Equity[n_, heads_, tails_] := Equity[n, heads, tails] = 
    If[n == 0, heads, 
       Max[1/2 + Equity[n - 1, heads, tails], 
           (heads + 1)/(heads + tails + 2) Equity[n - 1, heads + 1, tails] + 
           (tails + 1)/(heads + tails + 2) Equity[n - 1, heads, tails + 1]
           ]
      ]

For comparison, the Thompson sampling heuristic (which Cam Davidson Pilon claimed is optimal) gives an average of 60.2907 heads, lower by 1.03915. Thompson sampling has the problem that it sometimes samples B when you have enough information to know that it is not a good bet, and it often wastes chances to sample B early, when information is worth the most. In this type of problem, you are almost never indifferent between your options, and there is a pure optimal strategy.

tp[heads_, tails_] := tp[heads, tails] = 
    Integrate[x^heads (1 - x)^tails / Beta[heads + 1, tails + 1], {x, 0, 1/2}]


Clear[Thompson];
Thompson[flipsLeft_, heads_, tails_] := Thompson[flipsLeft, heads, tails] = 
    If[flipsLeft == 0, heads, 
       Module[{p = tp[heads, tails]}, 
           p (1/2 + Thompson[flipsLeft-1,heads,tails]) + 
           (1-p)((heads+1)/(heads+tails+2)Thompson[flipsLeft-1,heads+1,tails] + 
           ((tails+1)/(heads+tails+2)) Thompson[flipsLeft-1,heads,tails+1])]]
$\endgroup$
  • $\begingroup$ I agree that an optimal solution would be better than an approximate one. I wonder if there is an optimal general solution which can be efficiently applied within milliseconds in a dynamic environment with several hundred "coins". If not, I guess Thompson sampling is the best option. $\endgroup$ – M. Cypher Mar 15 '13 at 16:09
  • $\begingroup$ Thompson sampling is a poor approximation. There are better approximations you can use if you don't want to go through the trouble of the (at worst quadratic) exact calculation, but still want to avoid large errors. Actually, the exact calculation might be closer to linear. $\endgroup$ – Douglas Zare Mar 15 '13 at 16:33
  • $\begingroup$ What permits us to assume there is a prior distribution on B? I admit that such an assumption makes the problem more tractable, but the existence of an objectively valid assessment of the fairness of B is doubtful to me. Yes, we do have the results of some previous flips, but those are still consistent with any value for $\Pr_B(\text{heads})$ in $(0,1)$. If in fact that probability is less than $1/2$, then I don't care what prior you choose to adopt: it will be an objective fact that the expected number of heads with your approach is less than $50$. $\endgroup$ – whuber Mar 15 '13 at 19:06
  • $\begingroup$ I don't know Mathematica so I can't follow how you computed your expected number of heads. Care to explain that part? If we assume knowledge that coin B's bias is drawn from a uniform distribution on [0,1], then I don't see how you can expect to beat 50/50. $\endgroup$ – jerad Mar 15 '13 at 19:27
  • 1
    $\begingroup$ Douglas: Because I paid more attention to your answer :-). Please don't get me wrong--I like it and I like this thread. I thought it important to point out that you had to add an assumption in order to obtain your answer, that's all. As a practical matter, in many situations--including this one--there is no prior. (I sure wouldn't want to make up a personal prior and then have to bet big money on it!) But of course there is still an optimum, provided you specify a loss function. ("Maximizing" an expectation is not a full loss function.) $\endgroup$ – whuber Mar 15 '13 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.