Ah, but that proof is trivial, uninteresting, and utterly useless.
AIXI(tl) is basically brute-force search. The proof you reference shows that no program can do better than AIXI(tl) at general problem solving. Let’s taboo “AIXI(tl)”: no program can do better than brute-force search at general problem solving.
If you have any computer science training at all, alarm bells should be going off. There are exceedingly few real world problem domains where brute force is really the best algorithm. They are so rare and esoteric in fact that we collect and categorize them, with immediate application to cryptographic methods. Even then nearly all such identified problems have better-than-brute-force solutions, with sqrt reduction of the search space being a very common lower bound. Even in crypto, a true no-better-than-brute-force-search problem is a rare beast.
So what is going on here? As expected, the problem is in the assumed underlying definitions: no program can do better than AIXI(tl)/brute-force-search at general problem solving. What is general problem solving? Why, exactly the mathematically appealing definition of course: solving problems for which the agent has no a priori knowledge about the problem domain or solution space.
Looked at in this light, the proof very nearly becomes a tautology. Assuming the probability distribution of the solution space to be entirely flat and unstructured – that is to say, every candidate solution has equal probability of being a real solution, and finding bad solutions teaches you nothing about where the good solution might lay – means that no other search except brute-force enumeration of solution space is possible. Every form of search would either be a different enumeration of solutions (which has the same expected performance), or repeats solutions and therefore is less efficient. It’s not the best technique – it’s the only technique… assuming that there really is no information available about the problem domain and that the solution space is entirely unstructured.
However it is those assumptions that are ridiculous. The definition adopted by many AGI people is ability for an agent to solve problems it was not specifically programmed deal with. That in no way precludes using information about these new problems that can be extracted from the environment. And in real world use cases, there’s a lot of information available. Just as a trivial example, if nothing else a real embodied problem exists in a universe with the 2nd law of thermodynamics, which means that questions about efficiency and resource competition matter. Agents that are programmed to understand and give preference to such considerations will do better than agents which are not programmed as such (e.g. AIXI(tl)).
Or, to summarize this whole post: no agent can do better than AIXI(tl) at problems which meet some mathematical platonic ideal of randomness, but it is trivial to create a better agent than AIXI(tl) at problems encountered in the real world.
Your premise is incorrect. AIXIt is not brute-force search of solutions. It is a true self-optimizing search; see arxiv.org/abs/cs/0004001. AIXI itself isn’t a brute force search either. The basic AIXI model actually specifies no algorithmic implementation, so saying ‘brute force search’ is incorrect.
All your other arguments follow from this premise so they are also incorrect.
Solomonoff induction involves enumerating all possible program strings and testing for validity. There’s another term for the class of algorithms which behave this way in the literature: it’s called brute-force search.
(AIXI is not Solomonoff induction, it is reinforcement learning using Solomonoff induction to evaluate possible strategies. If I’m playing loose with terminology, it is here. But that technicality does not affect my argument.)
Ah, but that proof is trivial, uninteresting, and utterly useless.
AIXI(tl) is basically brute-force search. The proof you reference shows that no program can do better than AIXI(tl) at general problem solving. Let’s taboo “AIXI(tl)”: no program can do better than brute-force search at general problem solving.
If you have any computer science training at all, alarm bells should be going off. There are exceedingly few real world problem domains where brute force is really the best algorithm. They are so rare and esoteric in fact that we collect and categorize them, with immediate application to cryptographic methods. Even then nearly all such identified problems have better-than-brute-force solutions, with sqrt reduction of the search space being a very common lower bound. Even in crypto, a true no-better-than-brute-force-search problem is a rare beast.
So what is going on here? As expected, the problem is in the assumed underlying definitions: no program can do better than AIXI(tl)/brute-force-search at general problem solving. What is general problem solving? Why, exactly the mathematically appealing definition of course: solving problems for which the agent has no a priori knowledge about the problem domain or solution space.
Looked at in this light, the proof very nearly becomes a tautology. Assuming the probability distribution of the solution space to be entirely flat and unstructured – that is to say, every candidate solution has equal probability of being a real solution, and finding bad solutions teaches you nothing about where the good solution might lay – means that no other search except brute-force enumeration of solution space is possible. Every form of search would either be a different enumeration of solutions (which has the same expected performance), or repeats solutions and therefore is less efficient. It’s not the best technique – it’s the only technique… assuming that there really is no information available about the problem domain and that the solution space is entirely unstructured.
However it is those assumptions that are ridiculous. The definition adopted by many AGI people is ability for an agent to solve problems it was not specifically programmed deal with. That in no way precludes using information about these new problems that can be extracted from the environment. And in real world use cases, there’s a lot of information available. Just as a trivial example, if nothing else a real embodied problem exists in a universe with the 2nd law of thermodynamics, which means that questions about efficiency and resource competition matter. Agents that are programmed to understand and give preference to such considerations will do better than agents which are not programmed as such (e.g. AIXI(tl)).
Or, to summarize this whole post: no agent can do better than AIXI(tl) at problems which meet some mathematical platonic ideal of randomness, but it is trivial to create a better agent than AIXI(tl) at problems encountered in the real world.
Your premise is incorrect. AIXIt is not brute-force search of solutions. It is a true self-optimizing search; see arxiv.org/abs/cs/0004001. AIXI itself isn’t a brute force search either. The basic AIXI model actually specifies no algorithmic implementation, so saying ‘brute force search’ is incorrect.
All your other arguments follow from this premise so they are also incorrect.
Solomonoff induction involves enumerating all possible program strings and testing for validity. There’s another term for the class of algorithms which behave this way in the literature: it’s called brute-force search.
(AIXI is not Solomonoff induction, it is reinforcement learning using Solomonoff induction to evaluate possible strategies. If I’m playing loose with terminology, it is here. But that technicality does not affect my argument.)
It’s only brute-force search in the trivial sense that all search is brute-force search, at some level. See: No free lunch theorem.