You can directly compute the optimal strategy and its expected value with a dynamic program (backward induction).
Consider the possible states of the game, which can be completely described by the (number of -1 cards remaining, number of +1 cards remaining), with 16 possibilities.
Arrange them in a square grid as follows (it might be better on paper if you make it a diamond with (3,3) on the left and (0,0) on the right)
$$\begin{array}{ccccccc}
\stackrel{(0)}{(3,3)} & \rightarrow & \stackrel{(1)}{(3,2)} & \rightarrow & \stackrel{(2)}{(3,1)} & \rightarrow & \stackrel{(3)}{(3,0)}\\
\downarrow && \downarrow && \downarrow && \downarrow\\
\stackrel{(-1)}{(2,3)} & \rightarrow & \stackrel{(0)}{(2,2)} & \rightarrow & \stackrel{(1)}{(2,1)} & \rightarrow & \stackrel{(2)}{(2,0)}\\
\downarrow && \downarrow && \downarrow && \downarrow\\
\stackrel{(-2)}{(1,3)} & \rightarrow & \stackrel{(-1)}{(1,2)} & \rightarrow & \stackrel{(0)}{(1,1)} & \rightarrow & \stackrel{(1)}{(1,0)}\\
\downarrow && \downarrow && \downarrow && \downarrow\\
\stackrel{(-3)}{(0,3)} & \rightarrow & \stackrel{(-2)}{(0,2)} & \rightarrow & \stackrel{(-1)}{(0,1)} & \rightarrow & \stackrel{(0)}{(0,0)}\\
\end{array}
$$
The entries are on top (score if you stop here), bottom (#-1, #+1) remaining in the deck.
The trick is to work backwards from the (0,0) corner and decide at each state whether you want to continue or not. Examples:
- There is no decision at (0,0), it is worth 0.
- At (0,1) the choice is between taking -1, or drawing a card which gets 0. Since drawing is better, we now know (0,1) is also worth 0.
- At (1,0) we take 1 instead of drawing which gets 0.
- At (1,1) a real decision comes up. Stopping is worth 0. Drawing gets you 1/2 chance to move to (1,0) [worth 1] and 1/2 chance to move to (0,1) [worth 0]. So drawing is worth 1/2 on average, and it is optimal to do so.
You can continue filling in all the states to find the optimal strategy. Note that unequal card counts matter: at say (1,2), drawing gives you 1/3 chance to move to (0,2) and 2/3 chance to move to (1,1).
The filled in square looks like:
$$\begin{array}{ccccccc}
\stackrel{17/20}{(3,3)} & \rightarrow & \stackrel{6/5}{(3,2)} & \rightarrow & \stackrel{\mathbf{2}}{(3,1)} & & \stackrel{\mathbf{3}}{(3,0)}\\
\downarrow && \downarrow && &&\\
\stackrel{1/2}{(2,3)} & \rightarrow & \stackrel{2/3}{(2,2)} & \rightarrow & \stackrel{\mathbf{1}}{(2,1)} & \rightarrow^{?} & \stackrel{\mathbf{2}}{(2,0)}\\
\downarrow && \downarrow && \downarrow^{?} &&\\
\stackrel{1/4}{(1,3)} & \rightarrow & \stackrel{1/3}{(1,2)} & \rightarrow & \stackrel{1/2}{(1,1)} & \rightarrow & \stackrel{\mathbf{1}}{(1,0)}\\
\downarrow && \downarrow && \downarrow &&\\
\stackrel{0}{(0,3)} & \rightarrow & \stackrel{0}{(0,2)} & \rightarrow & \stackrel{0}{(0,1)} & \rightarrow & \stackrel{\mathbf{0}}{(0,0)}\\
\end{array}$$
States where you stop have their value bolded. At (2,1) it doesn't matter if you draw or stop.
Since you have made value-maximizing choices at every step including the effects of later choices, Strategy 2 is proven optimal, with value exactly 17/20.
Best Answer
First of all the expected value for the first pick is $(1+5+10+20)/4 = 9$
Then it depends on whether the bill is returned to be selected from.
If it's returned it's quite straight forward. The strategy must be that if you don't pick the 10 or 20 bill you try again. So in 25% of the cases you settle for your 20, 25% for the 10 and otherwise try again with an expected value of 9. So the result would be $20/4 + 10/4 + 9/2 = 12$.
If it's not returned the expected result of the second draw is dependent on the first bill:
So the result is that in 25% of the case we settle for 20, 25% we settle for 10, 25% we draw a second bill with the expected value of 31/3, and 25% we draw a second with the expected value of 35/3. So the result is
$${20 + 10 + 31/3 + 35/3\over 4} = {60+30+31+35\over12} = 13$$