The expected payoff of a dice game There's a question in my Olympiad questions book which I can't seem to solve:

You have the option to throw a die up to three times.  You will earn
the face value of the die.  You have the option to stop after each
throw and walk away with the money earned. The earnings are not additive. What is the expected payoff of this game?

I found a solution here but I don't understand it.
 A: Suppose you have only two rolls of dice. then your best strategy would be to take the first roll if its outcome is more than its expected value (ie 3.5) and to roll again if it is less.
Hence the expected payoff of the game rolling twice is:
\begin{equation}
\frac{1}{6}(6+5+4) + \frac{1}{2}3.5 = 4.25.
\end{equation}
If we have three dice your optimal strategy will be to take the first roll if it is 5 or greater otherwise you continue and your expected payoff will be:
\begin{equation}
\frac{1}{6}(6+5) + \frac{2}{3}4.25 = 4+\frac{2}{3}.
\end{equation}
A: This problem is solved using the theory of optimal stopping 
for Markov chains. I will explain some of the theory, then turn to your specific question. You can learn more about this fascinating topic in Chapter 4 of Introduction to Stochastic Processes by Gregory F. Lawler.

Think of a Markov chain with state space $\cal S$ as a game.
A payoff function 
 $f:{\cal S}\to[0,\infty)$
assigns a monetary "payoff'' to each state of the Markov chain. 
This is the amount you would collect if you stop playing with the
chain in that state. 
In contrast, the value function 
 $v:{\cal S}\to[0,\infty)$
is defined as the greatest expected payoff possible from each starting point;
$$v(x)=\sup_T \mathbb{E}_x(f(X_T)).$$ There is a single optimal strategy $T_{\rm opt}$
so that $v(x)=\mathbb{E}_x(f(X_{T_{\rm opt}})).$
It can be described as $T_{\rm opt}:=\inf(n\geq 0: X_n\in{\cal E})$, 
where ${\cal E}=\{x\in {\cal S}\mid f(x)=v(x)\}$. That is, you should stop playing as soon as you hit the set $\cal E$.

Example: 
You roll an ordinary die with outcomes $1,2,3,4,5,6$.
 You can keep the value or roll again.
If you roll, you can keep the new value or roll a third time.
After the third roll you must stop. You win the amount showing on the die.
What is the value of this game?
Solution:
The state space for the Markov chain is
$${\cal S}=\{\mbox{Start}\}\cup\left\{(n,d): n=2,1,0; d=1,2,3,4,5,6\right\}.$$
The variable $n$ tells you how many rolls you have left, and this decreases by one every
time you roll.  Note that the states with $n=0$ are absorbing.
You can think of the state space as a tree,
the chain moves forward along the tree until it reaches the end. 

The function $v$ is given above in green, while $f$ is in red.
The payoff function $f$ is zero at the start, and otherwise equals the number of spots on $d$.
To find the value function $v$, let's start at the right hand side of the tree.
At $n=0$, we have $v(0,d)=d$, and we calculate $v$ elsewhere by working backwards,
averaging over the next roll and taking the maximum of that and the current payoff.
Mathematically, we use the property $v(x)=\max(f(x),(Pv)(x))$ where $Pv(x)=\sum_{y\in {\cal S}} p(x,y)v(y).$
The value of the game at the start is \$4.66. The optimal strategy is to keep playing 
until you reach a state where the red number and green number are the same. 
A: Start from the end. 
What happens if you do not care about the first two rolls? The expected payoff is $(1+2+3+4+5+6)/6 = 3.5$. Now you have a freedom to go step earlier and make a decision about your strategy after the second roll (you still do not care about the first roll). We can actually find the optimal scenario which maximizes payoff:
$$E[X] = \frac{n}{6}3.5 + \frac{1}{6}[6+5+ \ldots+(n+1)] = \frac{n}{6}3.5 + \frac{1}{6}\cdot\frac{7+n}{2}(6-n)$$
It has a maximum for $n=3$ and then $E[X] = 4.25$. The meaning of the above expression is that if we roll $1,2,\ldots , n$ then we should roll once again. Otherwise we stop.
Ok, we move to the first roll and apply the same idea, but with a new expectation value $4.25$:
$$E[X] = \frac{n}{6}4.25 + \frac{1}{6}\cdot\frac{7+n}{2}(6-n)$$
Maximum is for $n=4$ and we get $E[X] = 4.6666...$.
In the problem the optimal strategy is the following:


*

*If you roll $1,2,3$ or $4$ in the first try, then reroll the dice. Otherwise take what you got, because on average you will not get more than $4.25$.

*In the second try. If you roll $1,2$ or $3$ you should roll once again. Otherwise stop, because on average you will not gain more than $3.5$. 

A: You have reframed the problem wherein you roll the dice simultaneously, and select the higher number.
The problem in question introduces the element of choice. You roll 1 dice. Then, you have the choice to reroll, but you must take the second result. 
For instance, you could roll a 2, and elect to roll again, getting a 1. But, you must keep this result. In this case your result has worsened, despite the option of a second roll.
This is why your answer is different. It is addressing a fundamentally different question. 
The Markov chain answer is the best, as it formally quantifies when you should elect to reroll. We know on a 6-sided dice when it makes sense to reroll. But when things get more complicated and this isn't immediately apparent, it's helpful to abstract that choice and find it arithmetically.
Best regards,
Alex
A: Let's suppose we have only 1 roll. What is the expected payoff? Each roll is equally likely, so it will show $1,2,3,4,5,6$ with equal probability. Thus their average of $3.5$ is the expected payoff.
Now let's suppose we have 2 rolls. If on the first roll, I roll a $6$, I would not continue. The next throw would only maintain my winnings of $6$ (with $1/6$ chance) or make me lose. Similarly, if I threw a $5$ or a $4$ on the first roll, I would not continue, because my expected payoff on the last throw would be a $3.5$. However, if I threw a $1,2$ of $3$, I would take that second round. This is again because I expect to win $3.5$.
So in the 2 roll game, if I roll a $4,5,6$, I keep those rolls, but if I throw a $1,2,3$, I reroll. Thus I have a $1/2$ chance of keeping a $4,5,6$, or a $1/2$ chance of rerolling. Rerolling has an expected return of $3.5$. As the $4,5,6$ are equally likely, rolling a $4,5$ or $6$ has expected return $5$. Thus my expected payout on 2 rolls is $.5(5) + .5(3.5) = 4.25$.
Now we go to the 3 roll game. If I roll a $5$ or $6$, I keep my roll. But now, even a $4$ is undesirable, because by rerolling, I'd be playing the 2 roll game, which has expected payout of $4.25$. So now the expected payout is $\frac{1}{3}(5.5) + \frac{2}{3}(4.25) = 4.\overline{66}$.
Does that make sense?
A: The following table exhibits the optimal play after two throws:
Throw 1    Throw 2     Action  Expectation

1          1           Throw    3.5
 1          2           Throw    3.5
 1          3           Throw    3.5
 1          4           Stop     4
 1          5           Stop     5
 1          6           Stop     6
 2          1           Throw    3.5
 2          2           Throw    3.5
 2          3           Throw    3.5
 2          4           Stop     4
 2          5           Stop     5
 2          6           Stop     6
 3          1           Throw    3.5
 3          2           Throw    3.5
 3          3           Throw    3.5
 3          4           Stop     4
 3          5           Stop     5
 3          6           Stop     6
 4          1           Throw    3.5
 4          2           Throw    3.5
 4          3           Throw    3.5
 4          4           Stop     4
 4          5           Stop     5
 4          6           Stop     6
 5          1           Throw    3.5
 5          2           Throw    3.5
 5          3           Throw    3.5
 5          4           Stop     4
 5          5           Stop     5
 5          6           Stop     6
 6          1           Throw    3.5
 6          2           Throw    3.5
 6          3           Throw    3.5
 6          4           Stop     4
 6          5           Stop     5
 6          6           Stop     6
Optimal play after two throws has the same expectation regardless of the value of the first throw, namely 4.25. Therefore, 
 it makes no sense to throw a second time if the first throw is greater than or equal to 4.25, 
 i.e. if you throw a 5 or a 6 on the first throw. Similarly, it always makes sense to throw a second time if the first throw is
 less than 4.25, i.e. if it's a 1, 2, 3 or 4.
Throw 1   Action  Expectation

1          Throw    4.25
 2          Throw    4.25
 3          Throw    4.25
 4          Throw    4.25
 5          Stop     5
 6          Stop     6
Finally, we compute the expectation of the game:
1/6*4.25+1/6*4.25+1/6*4.25+1/6*4.25+1/6*5+1/6*6=14/3=4.666...
A: Can someone explain to me why the expectation value of the outcome is not the same as the markov solution?
Imagine you were playing such that you cash out after 500 tries (instead of 2 or 3 treis).  On your first roll, you roll a 4.  Would you stop at the first roll because it's higher than 3.5?  I think not.  Your odds of getting a six are almost certain.  
What is the expectation value of rolling a die twice, while only keeping the highest value?  We can compute this as follows:
How many ways can I roll a 1?  The answer is 1.  1 on my first roll. (1) 
How many ways can I roll a 2?  The answer is 2.  Either on the first roll, (2) or on the second roll, assuming my first roll was a 1 (1,2).
How many ways can I roll a 3?  The answer is 3.  Either on the first roll (3) or on one of the second rolls, assuming my first roll was a 1,2 or 3 (1,3) (2,3).
And so on...
Therefore, there is only 1 outcome where I'd make \$1, two outcomes where I'd make \$2, 3 outcomes where I'd make \$3 dollars, up to 6 outcomes where I'd make \$6.
The total number of outcomes, then, is (1+2+3+4+5+6) = 21.
The expectation value is then:
$<E> = \$1 \frac{1}{21} + \$2\frac{2}{21} + \$3\frac{3}{21}$
$<E> = \frac{1}{21} \sum_{n=1}^{6} n^2$
$<E> = \$91/21 $
$<E> = \$4.3\bar{3}$
I guess I'm trying to answer the question "how much would you pay to play this game"?  I'd pay up to $4.333.
The other solutions look more sophisticated, so maybe I'm blowing smoke.
