Maximizing the number of heads in $N$ tosses by choosing which coin to toss 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} &gt; 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?
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 &lt; 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.