I am looking for a book explaining me theory and practice of problems common in interviews as:
throw one die, you can either win as much as it shows or re-throw. In the
second case you will accept anything it shows. What is the optimal strategy?
How much do you expect to win?
I honestly cannot understand well what domain these kind of problems are from, say game theory, stochastic control, dynamical programming, I find them labeled in different ways. I end up consulting dozens of books containing different things, and never find the "holy grail". I therefore look for a good textbook explaining how to "find the optimal strategy .. ", and an exercise book. Would you please give me any advice? I have no training on game theory or Markov decision processes.
This is an example of sequential problem that is solved using backward induction. It can be considered as a part of game theory, since one can treat it as a game, or decision analysis. The common way of answering such problems is to start from the end and then work out your way forward.
Probably some basic books on dynamic programming or sequential decision making are your best bet. But the general logic behind backward induction for such problems is pretty simple.
In this particular problem, we know that if you accept to throw a die again then, in expectations, you will receive $$ 1\times(1/6) + 2\times(1/6)+3\times(1/6)+4\times(1/6)+5\times(1/6)+6\times(1/6)=3.5 $$
Now, having this knowledge, let's consider the decision whether to choose to roll a die again. Let $x$ denote the outcome of the first roll. Then, comparing $x$ with the expected outcome of the second roll (that we have already computed) tells us that the decision rule should be
$$\text{accept to roll again if and only if }x<3.5$$
Thus, you should only roll again if you got $3$ or less in the first roll.
The expected outcome can be computed using the fact that you will re-roll with probability $1/2$ since w.p. $1/2$ you will get $3$ or less in the first roll.