3 ms·

So why is this happening? Some people are pointing at the error I mentioned above, but I think the problem is actually much deeper than that. Identifying this

So why is this happening? Some people are pointing at the error I mentioned above, but I think the problem is actually much deeper than that. Identifying this error is basically identifying the superficial reason for why they went wrong. It doesn't dig deep enough to systematically eliminate the error. I want to point out something. Notice their logic when they call out why it is a paradox. You can switch multiple times and it would never terminate. Mathematical formalism like markov decision processes and the bellman equations actually have the ability to capture this type of reasoning. They can even deal with infinite loops as happens here by including multiplication by a horizon term which makes the limit of the recursion equal to zero. So the root problem is that, actually, the entire problem wasn't even using the right theoretical grounding. To get really explicit on how it was not using the right grounding I want to point out the key error again, but stated a bit differently. The author neglects information sets. He creates two game trees, discriminating on the basis of knowledge of which subgame he is in. This is a huge red flag. You can do that in perfect information games, but you can't in imperfect information games! You aren't playing over states in imperfect information games. You're playing over information sets. You end up getting more insights into how this is wrong when you think about the problem in this way. For example, there might not be an error in this particular problem, but the choice to not express the action space as a probability vector is going to bite you in more complicated imperfect information decision problems.

JoshCole 4y ago
On reflection, it bites you on this particular problem too, because when you take the limit of P(Switch=1) the recursive switch case with a discount factor under the formalism mentioned above is zero. So for every strategy selection except the one the article chooses, the EV is what I mentioned before. But for the last it is zero. Its the same problem: they aren't walking the graph of the game tree. But its a bit different to my simplified version of the game that shows where there EV calculations went super wrong, because the actual game tree is of infinite length and there is /never/ a node with SWITCH that terminates in a reward, because every SWITCH recurses to another decision point. You can solve it using various formalism by adding a discount factor. That lets the limit go to zero for the recursive cases. I guess technically its undefined since the game never ends, but I don't consider being stuck in a loop to be rational [1]. You really have to let your action probabilities vary as you solve imperfect information problems. It happens in MDP and MCCFR for a reason - you don't get the correct action without for the way your policy choice affects the outcome distribution. Your expectation is dependent on your policy it doesn't exist in a void. That last statement, well, it should be very obvious in more complex situations. That it isn't obvious in this situation speaks to the problems deceptive simplicity. [1]: Unlike people who think humans are irrational for having cognitive biases.

JoshCole 4y ago

On reflection, it bites you on this particular problem too, because when you take the limit of P(Switch=1) the recursive switch case with a discount factor under the formalism mentioned above is zero. So for every strategy selection except the one the article chooses, the EV is what I mentioned before. But for the last it is zero. Its the same problem: they aren't walking the graph of the game tree. But its a bit different to my simplified version of the game that shows where there EV calculations went super wrong, because the actual game tree is of infinite length and there is /never/ a node with SWITCH that terminates in a reward, because every SWITCH recurses to another decision point. You can solve it using various formalism by adding a discount factor. That lets the limit go to zero for the recursive cases. I guess technically its undefined since the game never ends, but I don't consider being stuck in a loop to be rational [1]. You really have to let your action probabilities vary as you solve imperfect information problems. It happens in MDP and MCCFR for a reason - you don't get the correct action without for the way your policy choice affects the outcome distribution. Your expectation is dependent on your policy it doesn't exist in a void. That last statement, well, it should be very obvious in more complex situations. That it isn't obvious in this situation speaks to the problems deceptive simplicity. [1]: Unlike people who think humans are irrational for having cognitive biases.