Two envelopes problem

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.

It is trivial! It is trivial!

The game defines a graph and your path through that graph is going to lead to an outcome. You have a strategy, a choice of how to move through the graph. However, you have no information about where you are in the graph. So when we think about how we move through the graph, we must always think the same way. We can never think differently, because no action changes the information we have about where we are. However, the terminal case is defined thusly. R(STAY) = {50%: 2A, 50% A}. There is never a reward for R(SWITCH). Anyone telling you to always choose switch when that is the only solution that can never have a reward is obviously wrong.

But why? Why were they wrong?

Simple. In imperfect information games things work differently than in perfect information games. In chess when you make a move it is that move. If you make a move it is a different move. The subgames are independent of each other. In poker, it isn't so! If you make a bet in Poker, you don't know what subgame you are in. You have to play as if you're in multiple at the same time.

Now look at the fast con that seems to be tripping people up. They are pretending we have perfect information. 2A, A/2? Phaw. We can't have that, because that supposes we know which subgame we are in, but we can't know which subgame we are in, because we were never given that information. Even if we were - it doesn't matter. We're in an imperfect information game! The places we didn't explore are relevant to our calculation! We can't ignore them! But we did, by insisting on an inequality which didn't hold.

This is probably counterintuitive. Its trivial, but people argue about it. So lets talk about this more concretely.

This is what they pulled on you. They claimed that these two different game trees could be treated as the same game tree:

             -> Keep    -> 2A
          2A -> Switch  -> A
    0.5 ->
          A  -> Keep    -> A
             -> Switch  -> 2A

                -> Keep    -> A
          A     -> Switch  -> A/2
    0.5 ->
          A/2   -> Keep    -> A/2
                -> Switch  -> A

Two different game trees! Two different game trees and they acted like they were the same. But they aren't! They can't be! You can't tell which subgame you are in you have to treat them as equal in imperfect information games! So what is our actual situation with their reasoning? Our actual situation is a contradiction. Since subgames depends on each other when they do this combination they are secretly speaking nonsense. Look closely: They are claiming that 2A=A; that A=A/2. They have to be, because in imperfect information games we have to be in every subgame at once, but they made two different games, but then they combined them. Since the correct formulation has to have every solution treated as the same, but they took something from a different subgame, they declared that two subgames were equal, but they weren't.

It is so trivial. That's why the correct calculation looks like only an expectation on one game tree. That's why it seems to make sense - your brain knows this sort of reasoning can be appropriate with perfect information. I realize a lot of people have argued about this, but frankly they should stop.

And if you're interested in exploring why you have to treat subgames as different in imperfect information, why you have to operate on information sets rather than state spaces in imperfect information, here is a great talk on the NIPS 2017 Best Paper award which happens to touch on the subject:

https://www.youtube.com/watch?v=tRiaGahlyy4

It is about solving poker, which is a much more complicated imperfect information game. But even the simple imperfect information games have this property.

No, he articulated the problem correctly. He's just wrong that the math isn't with him. Game theory solves imperfect information games using information sets. The math is with him.

In imperfect information games you are in an information set, not a subgame. When the value is 2A and you have to make a keep or switch decision, the value A is still part of how you calculate the solution. When the value A is the game you are in, it doesn't matter, the value 2A is still part of how you calculate the solution. It has to be this way, because you don't have a way of discriminating between which game state you are in. This is one of the notable and counterintuitive (apparently) results of game theory and it really matters, because when you don't notice it you run into a contradiction.

Check out Noam's talk on solving imperfect information games at NIPS 2017 for a more detailed treatment of this subject. I'm going to handwave it to dive deeper into the exact logical contradiction.

So 2A and A both have to exist still for the correct calculation. The subgames are still connected. But notice what happens? What the failed solution does though is it creates two different subgames!

In one they set 2A. In another they have A/2. But its still two different subgames. Now why does this seem appropriate? Because this sort of reasoning is okay in perfect information games! You can reason about different subgames independently of each other.

But we're not in a perfect information game. We're in a null information set. So 2A and A coexist.

Since we can't state that we are in the 2A case or the A case, being in an information set that prevents us from discrimination between these two things, they error when they try to build their reasoning on the supposition they are able to do so. In particular, they create a logical contradiction.

The dependence means you are required to have the subgame from the 2A as the other side of the equation. Required, but they don't do that. Instead they evaluate one subgame as if they are in a perfect information context.

That is the missing equality symbol that people aren't seeing. That dependence. So what is really happening is this: They claim 2A=A; assuming A is not zero, they claim that 2=1. You can see this very clearly when you take the actual correct probabilities for expectation and place them beside the incorrect ones:

Observe.

    They said: 5/4A = (1/2)2A + (1/2)A/2
    Reality  : 3/2A = (1/2)2A + (1/2)A
    Equality : (1/2)2A + (1/2)A/2 = (1/2)2A + (1/2)A
                         (1/2)A/2  = (1/2)A
                              A/2  =  A
                              A    = 2A
                              1    = 2

It's a bit worse than that in the error, because they omit that expectation is a function of both policy and information set. Trying to make the decision based on expected value when expected value is not well defined without a policy choice is another very fundamental error. I mean seriously, ask yourself if you get the same result by slamming your head into a wall as opposed to doing something productive. You don't. Policy choice matters. In this case literally the only policy choice that has 0 EV is the one they claim is the best. Its silly. When you look at the game tree, when you actually evaluate the proper graph, its literally the only bad decision you can make. There are quite literally an infinite number of strategies that give the same EV solution. All except the one they chose.

The reward for the game is only defined for R(KEEP) and it is defined as {0.5: A, 0.5: 2A}. R(SWITCH) ends up getting its valuation according to a bellman equation: R(SWITCH) = R(SWITCH) * P(SWITCH) + R(KEEP) * P(KEEP). This is obviously an infinite sequence if P(SWITCH) = 1. We actually tend to use a discount factor here like 0.9999999999*R(some_choice) because for this infinite sequence it lets us use limits to claim the case is defined as 0.

But this is like, an extension of why this is wrong - because game theory with information sets already solves for probabilities over action space. It already acknowledges it. So when you point to the information set problem? You point to game theory. And you point to the root of why their calculations were wrong: in an imperfect information game, you play both the game you're in and the game you're not in at the same time.

> halving the probability of each value as he does in the video we take 1/20

but then the probabilities don't all add up to 1.