7
$\begingroup$

Assume you have two coins $A,B$ with biases $P_A,P_B$ respectively. We would like to make $N$ coin tosses and get the maximal number of heads possible. Unfortunately, we know $P_B$, but $P_A$ is unknown at the beginning of the process.

What is the best possible strategy for selecting which coin to toss at each step?

Note: I'm looking for actual optimization of the selection, not heuristic methods. You may assume a reasonable prior distribution on $P_A$ if needed.


EDIT:

Here is a formal definition of the objective. Let $P_A,P_B\in (0,1)$ and $P=max\{P_A,P_B\}$. The optimal strategy in hindsight will achieve on average $P\cdot N$ head tosses. Let $a(P_A,P_B)$ be the expected number of times our strategy picked coin $A$ given that the probabilities were $P_A,P_B$.

The Optimization Objective: minimize the expected regret, i.e. $$Regret=P\cdot N - P_A\cdot a(P_A,P_B) - P_B\cdot (N-a(P_A,P_B))$$

The Goal: Devise a selection strategy that guarantees (expected) $Regret\leq r$ for any values of $P_A,P_B$ (for the smallest value of $r$ possible).

Note that if $P_A\approx P_B$ this is not a problem in this definition as it means our regret will be small regardless of which coin we flip.


If $N$ is unknown (i.e. the process may end arbitrarily after an adversarialy chosen number of tosses), the best strategy would be to occasionally explore coin $A$ to get a better $\widehat {P_A}$ estimation, and in the rest of the time toss coin $A$ iff $\widehat {P_A} > P_B$.

In the scenario $N$ is known, it's not hard to argue that the optimal strategy makes a series of tosses of coin $A$ and then either keeps on tossing $A$ for the remaining tosses or starts tossing only coin $B$, but how can we optimize the cutoff (i.e. the switch to tossing coin $B$) to maximize the expectancy of head results?

$\endgroup$
  • 1
    $\begingroup$ I disagree, if I understood your last statement correctly. While I agree that first we should toss A and then B, there need not be a cut-off. Image that first it seems that $P_A>P_B$, so we start tossing A and then it turns out that most probably $P_A<P_B$. In this case we would like to switch to B. $\endgroup$ – domotorp Jun 23 '14 at 16:47
  • 1
    $\begingroup$ I also think this question is more suitable for mathoverflow. $\endgroup$ – domotorp Jun 23 '14 at 16:48
  • $\begingroup$ @domotorp - What I meant by cutoff is that once (and if) we switch to tossing coin $B$, we will not toss $A$ ever again (in the optimal strategy), so the question becomes when to make the switch given the current sequence of $A$ tosses. $\endgroup$ – R B Jun 23 '14 at 22:10
  • $\begingroup$ What measure are you using, to define "best" possible strategy? Expected performance? Worst-case performance, over the worst possible value of $P_A$ (and $N$, if $N$ is not known)? If we have a Bayesian prior on $P_A$, then it sounds like you might be talking about expected performance (expectation taken with respect to $P_A$). $\endgroup$ – D.W. Jun 23 '14 at 23:04
  • $\begingroup$ For your second case, a strategy is basically a function $f:\{1,2,\dots,N\}\to \{0,1,2,\dots,N\}$ that says: if you've tossed $A$ for $k$ times and if the number of heads is $< f(k)$, then switch to tossing $B$. For any fixed $N$, you should be able to find the optimal strategy using dynamic programming. Each subproblem is: suppose that after $k$ flips, we have seen $h$ heads and have/haven't switched to tossing coin $B$; then what's the optimum strategy from here on? There are only $O(N^2)$ subproblems. $\endgroup$ – D.W. Jun 23 '14 at 23:14
2
$\begingroup$

I agree with D.W. that this should just be a dynamic programming question. Assume that $P_B$ is known and that we have a prior on $P_A$ and that $N$ is known. (Without a prior on $P_A$ or a known $N$, I do not see how your objective or "optimal" are well-defined.) Let optimal mean "maximizes expected number of heads" with the expectation over both the coin flips and the draw of $P_A$ from the prior. (This seems to me the only natural definition of (edit: achievable) "optimal" here.)

Let $Val(t,prior)$ be the expected number of heads of the optimal strategy starting at time $t$ with prior $prior$ on $P_A$. Then immediately $$ Val(N,prior) = \max\{ P_B, ~ \mathbb{E}P_A \} $$ since at the last step we should just choose the higher chance of flipping heads, and $\mathbb{E}P_A$ with respect to $prior$ is the probability of getting heads from flipping coin $A$. So we know how to choose the coin at the last step for any distribution on $P_A$.

At step $t < N$, $$ Val(t,prior) = \max\{ P_B + Val(t+1,prior), ~~ \text{val if flip $A$}\} $$ where $$ \text{val if flip $A$} ~~ = \mathbb{E}P_A ~~ + (\mathbb{E}P_A) Val(t+1,posterior(prior,heads)) ~~ + (1-\mathbb{E}P_A) Val(t+1,posterior(prior,tails)) . $$

Explanation: The value for flipping $B$ is $P_B$ for this coin flip, plus the value of the optimal strategy at time $t+1$ with the same prior on $P_A$ as we currently have. The value for flipping $A$ is the expected number of heads for this round, $\mathbb{E}P_A$, plus our expected value over the two possible cases. First, if the coin comes up heads (which happens with probability $\mathbb{E}P_A$), then we will update our prior to a posterior on $P_A$ conditioned on that event, and we will play the optimal strategy at time $t+1$ with that new distribution. Similarly if it comes up tails.

There are at the very most $O(n^3)$ cases to calculate because there are $N$ time steps, and at each time step $t$, we have a distribution on $P_A$ that consists of the original prior updated after observing $j=0,\dots,t$ heads and $k=0,\dots,t-j$ tails. But this should be reduced with your observation that we need only consider strategies that try $A$ for some amount of time, then (optionally) flip $B$ for the rest of the time.

Why this is optimal: Assume that the strategy is optimal at time $t+1$ for the specified prior distribution. But the "correct" prior distribution is always exactly the one we plug in to the formula: After observing a heads, the correct distribution over $P_A$ is precisely $posterior(prior,heads)$, and so on. When I say correct, what I mean is that the posterior gives the exact distribution over $P_A$ given that $P_A$ is drawn from the prior and these outcomes are observed. So we really are maximizing over the "average case" in each given scenario.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I disagree. The optimal solution value is $N\max \{P_A,P_B\}$, where $P_A$ was drawn from the prior distribution. In fact, you could occasionally beat $N\max \{\mathcal{E} P_A,P_B\}$, where $\mathcal{E} P_A$ is the expectation of the prior of $A$, as you can learn the actual value of $A$ through sampling. $\endgroup$ – R B Jun 24 '14 at 22:19
  • $\begingroup$ @RB, I don't understand your comment. The optimal solution value is the expected value of the best strategy, where "expected value" is as defined in the first paragraph of this answer. You seem to be assuming there exists a strategy whose expected value is $N \max(P_A,P_B)$. I don't see how to construct a strategy with that expected value. (Remember, the expectation is over not just the coin flips but also the random choice of $P_A$.) $\endgroup$ – D.W. Jun 25 '14 at 0:39
  • $\begingroup$ @RB, to expand on D.W.'s point, I think the way to look at it is: sure, we could compare to some "omniscient" optimal and try to do our best relative to that, but either way "do our best" means "maximize our expected number of heads", so I'm not sure it helps to think about this omniscient optimal solution. ... In a case where the optimal achievable strategy is not well-defined or is unknown, it makes sense to define some upper-bound and talk about approximation ratio or regret relative to that. But if we can define a single best strategy, then I'm not sure regret is helpful. $\endgroup$ – usul Jun 25 '14 at 1:57
  • $\begingroup$ @D.W - There doesn't has to be a way to construct a $N\max(P_A,P_B)$ strategy to compare ours to it.. In fact, this is done frequently in regret minimization, you compare yourself to the best offline strategy. Beating $N\max\{\mathbb{E}P_A,P_B\}$ is sometimes trivial (consider $P_B=0.5$ and $P_A\in\{0,1\}$ uniformly - you can easily beat it w.p. 1/2). $\endgroup$ – R B Jun 25 '14 at 6:05
1
$\begingroup$

This question can be reduced to that of an online auction of a digital good, the optimization of which is structured in a similar way.

For example, imagine there are $N$ bidders in an auction, and you -- the auctioneer -- would like to maximize your revenue. Each bidder has some valuation for the object that we can assume is drawn from a reasonable prior distribution. The auctioneer posts a price, and he has the option of taking it or leaving it.

The auctioneer can post any price in the set $X = {x_1, ..., x_n}$ –- and without loss of generality we can assume $X \in [0, 1]$. There is some optimal, fixed price, that maximizes your revenue so your regret is $P_{fixed} - Empirical$.

And the question of the algorithm used to generate $Empirical$ is very well-studied in economics and auction theory.

You're asking the same question, for 100 items and 2 bidders. A heads is analogous to a bidder accepting a posted price and the coins are like the prices themselves.

You could start with Online Learning in Online Auctions for a host of optimal strategies for your play. One option is a variant of the fairly well-known weighted majority voting algorithm, which guarantees a regret that grows as a square root of the number of bidders.

| cite | improve this answer | |
$\endgroup$

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.