4 ms·
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. T
by JoshCole 4y ago
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.