= 27d567bc2d48d9f40e9ccc20ea370b15)
cousin_it comments on The Rhythm of Disagreement - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (65)
With all due respect, that's not quite the sort of answer I want... Eliezer made a sharp mathematical statement, I made another. Can you reformulate your comment as a sharp mathematical statement too, so I can see if it's a fair rephrasing of Eliezer's statement?
I apologize! My point is - you can't calculate the "expected benefit" of the algorithm after making an assumption about the distribution of the money. The expected benefit is the average benefit of the algorithm over all possible distributions (weighted by likelihood). Assuming we know nothing about the likelihood of specific distributions, the probability that there is a difference between f(x1) and f(x2) is ~0. By "density of the differential", I believe he is referring to the fact that in order for there to be a difference between those two numbers, f ' will have to be "dense" on some part of the interval between them. Since we don't know where that is, we can't decide where to concentrate the function's differential. Is this sufficiently formal / sensible?
That's... still not very precise, but I also apologize, because I can't really explain how to think precisely. I was kinda born this way and have no idea of the typical difficulties. Maybe you could look at my reply to JGWeissman as an example of what can be said precisely about the problem? It shows that Thrun's algorithm can give a large (constant) benefit even if values of f(x) have arbitrarily small differences. That seems to contradict your comment, but I can't really tell :-)
It's not that I don't know how to think precisely about math! I was attempting to translate a fairly vague concept. Though I think I was in error about the selection of dollar values, I had overlooked that one is always twice the other, it sounded like Eliezer was implying they were close to each other. So I'm not certain that my interpretation of what Eliezer was saying is a correct analysis of the problem (in fact no matter what he was actually saying, it has to have been an incorrect analysis of the problem given that you have provided a counterexample to his conclusion, yes?), though it still looks to me as though he was saying that the integral of df/dx in some region about "the vicinity of the actual envelope contents" is expected to be low (though I, and I suspect he, would use the integral of df/dx on the interval from x to 2x).
The argument makes sense if you assign utility 1 to choosing correctly and utility 0 to choosing incorrectly, I think. And in fact, rereading the post, this seems to be the intent!
It also still looks to me that your statement "the expected benefit of the algorithm is 1 dollar" above uses an incorrect interpretation of "expected benefit" (I think the expected benefit of the algorithm using that function is 0).
I took a look at your reply to JGWeissman, and yep, it looks like the algorithm works, which is neat! I'd contest the description of 25 cents as a large constant benefit, but certainly there are ways to increase it (how high, I wonder?).
Thus - my interpretation of Eliezer's argument holds that you can't get above an expected 50% chance of picking the better envelope, but that example does show that you can get higher expected value than 3/2 x. Therefore, no contradiction?
The expected benefit is 25 cents if the minimum possible contents of an envelope is 1 dollar. More generally, if envelopes are guaranteed to contain more than 100 dollars, then using f(x)=100/x yields expected benefit of 25 dollars, and so on. Also, Eliezer is right that a randomized algorithm can't be Bayesian-optimal in this problem, so for any given prior there's a deterministic algorithm with even higher expected benefit, I guess you can work it out.
1/4 of the smallest possible amount you could win doesn't count as a large constant benefit in my view of things, but that's a bit of a nitpick. In any case, what do you think about the rest of the post?
Oh, sorry, just noticed the last part of your comment. It seems wrong, you can get a higher than 50% chance of picking the better envelope. The degenerate case is if you already know there's only one possibility, e.g. 1 dollar in one envelope and 2 dollars in the other. If you open the envelope and see 1 dollar, then you know you must switch, so you get the better envelope with probability 100%. You can get more fuzzy cases by sort of smearing out the distribution of envelopes continuously, starting from that degenerate case, and using the f(x) strategy. The chance of picking the better envelope will fall below 100%, but I think it will stay above 50%. Do you want my opinion on anything else? :-)
That's definitely cheating! We don't have access to the means by which X is generated. In the absence of a stated distribution, can we still do better than 50%?
Well, Thrun's algorithm does better than 50% for every distribution. But no matter what f(x) we choose, there will always be distributions that make the chance arbitrarily close to 50% (say, less than 50%+epsilon). To see why, note that for a given f(x) we can construct a distribution far enough from zero that all values of f(x) are less than epsilon, so the chance of switching prescribed by the algorithm is also less than epsilon.
The next question is whether we can find any other randomized algorithm that does better than 50%+epsilon on any distribution. The answer to that is also no.
1) Note that any randomized algorithm must decide whether to switch or not, based on the contents of the envelope and possibly a random number generator. In other words, it must be described by a function f(x) like in Thrun's algorithm. f(x) doesn't have to be monotonic, but must lie between 0 and 1 inclusive for every x.
2) For every such function f(x), we will construct a distribution of envelopes that makes it do worse than 50%+epsilon.
3) Let's consider for each number x the degenerate distribution D_x that always puts x dollars in one envelope and 2*x in the other.
4) To make the algorithm do worse than 50%+epsilon on distribution D_x, we need the chance of switching at 2*x to be not much lower than the chance of switching at x. Namely, we need the condition f(2*x)>f(x)-epsilon.
5) Now we only need to prove that there exists an x such that f(2*x)>f(x)-epsilon. We will prove that by reductio ad absurdum. If we had f(2*x)≤f(x)-epsilon for every x, we could iterate that and obtain f(x)≥f(x*2^n)+n*epsilon for every x and n, which would make f(x) greater than 1. Contradiction, QED.
Yes, that all looks sensible. The point I'm trying to get at - the one I think Eliezer was gesturing towards - was that for any f and any epsilon, f(x) - f(2x) < epsilon for almost all x, in the formal sense. The next step is less straightforward - does it then follow that, prior to the selection of x, our expectation for getting the right answer is 50%? This seems to be Eliezer's implication. However, it seems also to rest on an infinite uniform random distribution, which I understand can be problematic. Or have I misunderstood?
As for the deterministic variant, as you'd need some distribution from which the value of x is being selected, I'm not sure how best to calculate the EV of any particular scheme (whereas the nondeterministic algorithm sidesteps this by allowing a calculation of EV after X is selected). With a good prior, yeah, it'd be pretty simple, but without it becomes GAI-complete, yeah?
I think the claim is that there must a deterministic algorithm that does at least as well as the randomized algorithm. The randomized algorithm is allowed to be optimal, just not uniquely optimal.
Oh. Sorry. You're right.