Solomonoff prior

The 'universal prior' gives probability $2^{-K}$ to all sequences that can be generated by a $K$-bit program. Generally a sequence is generated by multiple programs of different lengths, so you sum the probabilities. It doesn't matter how quickly the program runs. Solomonoff probabilities are closely related to Kolmogorov complexity and are similarly uncomputable, and only defined up to a constant, corresponding to the program encoding.

Is this a useful concept?

This nostalgebraist comment codifies some damning observations about theories of rational behavior that rely on Solomonoff induction:

… By construction, any agent you can actually design and run is a single element of S (a "practical strategy"), so every fact about rationality that can be incorporated into agent design gets "hidden inside" the individual s∈S, and the only things you can learn from the "ideal theory" R are things which can't fit into a practical strategy.

For example, suppose (reasonably) that model averaging and complexity penalties are broadly good ideas that lead to good results. But all of the model averaging and complexity penalization that can be done computably happens inside some Turing machine or other, at the level "below" Solomonoff. Thus Solomonoff only tells you about the extra advantage you can get by doing these things uncomputably. Any kind of nice Bayesian average over Turing machines that can happen computably is (of course) just another Turing machine.

This also explains why I find it misleading to say that good practical strategies constitute "approximations to" an ideal theory of this type. Of course, since R just says to follow the best strategies in S, if you are following a very good strategy in S your behavior will tend to be close to that of R. But this cannot be attributed to any of the searching over S that R does, since you are not doing a search over S; you are executing a single member of S and ignoring the others. Any searching that can be done practically collapses down to a single practical strategy, and any that doesn't is not practical. Concretely, this talk of approximations is like saying that a very successful chess player "approximates" the rule "consult all possible chess players, then weight their moves by past performance." Yes, the skilled player will play similarly to this rule, but they are not following it, not even approximately! They are only themselves, not any other player.

Agents in the universal prior?

Paul Christiano argues that Solomonoff priors are malign. Essentially, they are bad priors because they're universal; they put huge amounts of mass on stuff that doesn't look like the real world. Meanwhile, because they contain everything, they contain lots of explanations for sequences that look like 'this sequence is occurring inside a dream / simulation being run by a rational agent'. It takes extra bits to specify the rational agent, but that rational agent then probably mostly dreams about things that 'make sense' as plausible worlds, so encoding things in those terms saves a lot of bits versus the 'dumb' direct prior which dreams about huge numbers of non-plausible worlds. So the shortest encoding of our observations under the universal prior might go through a simulation of an intelligent agent.

One illustrative analogy is to imagine that we have a 'bad' Python interpreter in which all letters outside of a literal must be repeated 10 times, so to print "Hello, world" we have to write

pppppppppprrrrrrrrrriiiiiiiiiinnnnnnnnnntttttttttt("Hello, world!")

Even for this simple program, it turns out to actually be shorter to invoke a 'smarter' interpreter that allows for a more compact encoding of the problem:

eeeeeeeeeevvvvvvvvvvaaaaaaaaaallllllllll("print('Hello, world!')")

Paul's argument, which isn't fully obvious to me, but I guess not obviously wrong, is that the analogous 'smarter interpreter' for observations of our world might look like "the dream of a rational agent", and that such agents might have goals other than just faithfully extrapolating our world.

More succinctly: compressing a string is one of the simplest possible 'objective functions', but it can still produce mesa optimizers.