Game 1: on each round you and Omega state your probabilities that the next bit will be 1. The logarithm of the probability you assigned to the actual outcome gets added to your score. [...] As it turns out, in game 1 you cannot beat Omega by more than an additive constant, even if the input sequence is uncomputable and you know its definition.
I don’t get this. A trivial algorithm always assigning p(0) = p(1) = 1⁄2 will have its score dropping by |log(1/2)| for each bit. At the same time, with the bit sequence maximally hostile to Omega, where b_{n+1} = ~OmegaPrediction((b_1...b_n)), Omega’s score will always drop by at least |log(1/2)| and typically more, sometimes far more (whenever it hyper-computes any probabilities very far from 1⁄2).
Unless I’m missing something (as I probably am), how can the difference between the score of the trivial algorithm and Omega remain limited to “an additive constant” in any sense of the term?
That seems to be equivalent to saying that Omega’s probability estimates will approach fifty-fifty fast enough. So if I understand correctly, it’s a provable property of Solomonoff induction that faced with a “maximally hostile” bit-string, its probability estimates will converge to fifty-fifty fast enough that it can’t blunder worse than a random guesser by more than a constant term in the log(P) game? If true, I find that quite fascinating.
Let’s regard Omega’s prior as being given by M(x) as shown here. Now let’s divide our monotone UTM’s programs into the following classes.
Ones that just say “Print the following: … ”
Every other program.
You can imagine Omega as a Bayesian reasoner trying to decide between the two hypotheses “the data was generated by a program in class 1” and “the data was generated by a program in class 2″. Omega’s prior will give each of these two hypotheses a non-zero probability.
To “cut to the chase”, what happens is that the “extra damage” to the score caused by “class 2” falls off quickly enough, relative to the current posterior probability of “class 2″, that the extra loss of score has to be finite.
Yes, it’s a provable property of Solomonoff induction. It was a surprise to me too when I worked it out some days ago (using Shane Legg’s paper linked from the post), but users AlephNeil and paulfchristiano didn’t seem surprised, and Eliezer always considered it obvious I guess.
But then it seems to me that Game 3 is unfair, in that it artificially amplifies infinitesimal errors. Faced with a hostile input, a Solomonoff predictor will correctly converge to saying “I don’t know,” i.e. producing p(0) ~ p(1) ~ 1⁄2. However, a game that forces it to nevertheless make binary predictions in this situation will force an answer based on the infinitesimal differences between the calculated probabilities and 1⁄2, and moreover, the correct answers are contrived so that these infinitesimal differences always point in the wrong direction.
If you instead let the Solomonoff predictor just honestly say “I don’t know,” as in the first two games, the problem disappears.
If you instead let the Solomonoff predictor just honestly say “I don’t know,” as in the first two games, the problem disappears.
True, though sometimes in real life, you can’t just say “I don’t know”, you have to choose an action. Game 3 is unfair, but real life can be unfair too.
I don’t get this. A trivial algorithm always assigning p(0) = p(1) = 1⁄2 will have its score dropping by |log(1/2)| for each bit. At the same time, with the bit sequence maximally hostile to Omega, where b_{n+1} = ~OmegaPrediction((b_1...b_n)), Omega’s score will always drop by at least |log(1/2)| and typically more, sometimes far more (whenever it hyper-computes any probabilities very far from 1⁄2).
Unless I’m missing something (as I probably am), how can the difference between the score of the trivial algorithm and Omega remain limited to “an additive constant” in any sense of the term?
The drop in Omega’s score on each step will approach |log(1/2)| fast enough that the two sums won’t differ by more than a constant.
That seems to be equivalent to saying that Omega’s probability estimates will approach fifty-fifty fast enough. So if I understand correctly, it’s a provable property of Solomonoff induction that faced with a “maximally hostile” bit-string, its probability estimates will converge to fifty-fifty fast enough that it can’t blunder worse than a random guesser by more than a constant term in the log(P) game? If true, I find that quite fascinating.
Let’s regard Omega’s prior as being given by M(x) as shown here. Now let’s divide our monotone UTM’s programs into the following classes.
Ones that just say “Print the following: … ”
Every other program.
You can imagine Omega as a Bayesian reasoner trying to decide between the two hypotheses “the data was generated by a program in class 1” and “the data was generated by a program in class 2″. Omega’s prior will give each of these two hypotheses a non-zero probability.
To “cut to the chase”, what happens is that the “extra damage” to the score caused by “class 2” falls off quickly enough, relative to the current posterior probability of “class 2″, that the extra loss of score has to be finite.
I see! That’s a very good intuitive explanation, thanks for writing it down.
Yes, it’s a provable property of Solomonoff induction. It was a surprise to me too when I worked it out some days ago (using Shane Legg’s paper linked from the post), but users AlephNeil and paulfchristiano didn’t seem surprised, and Eliezer always considered it obvious I guess.
But then it seems to me that Game 3 is unfair, in that it artificially amplifies infinitesimal errors. Faced with a hostile input, a Solomonoff predictor will correctly converge to saying “I don’t know,” i.e. producing p(0) ~ p(1) ~ 1⁄2. However, a game that forces it to nevertheless make binary predictions in this situation will force an answer based on the infinitesimal differences between the calculated probabilities and 1⁄2, and moreover, the correct answers are contrived so that these infinitesimal differences always point in the wrong direction.
If you instead let the Solomonoff predictor just honestly say “I don’t know,” as in the first two games, the problem disappears.
True, though sometimes in real life, you can’t just say “I don’t know”, you have to choose an action. Game 3 is unfair, but real life can be unfair too.