then an AIXI that follows one prior can be arbitrarily stupid with respect to another.
Yet another application of David Wolpert’s No Free Lunch theorems.
We have dubbed the associated results NFL theorems because they demonstrate that if an algorithm performs well on a certain class of problems then it necessarily pays for that with degraded performance on the set of all remaining problems.
NFL works with algorithms operating on finite problems. With algorithms operating on unbounded problems, you can benefit from Blum’s speedup theorem: for every algorithm and every computable measure of performance, there’s a second algorithm performing better than the first on almost all inputs.
I suspect here’s happening something similar: AIXI is finitely bias-able, and there are environments that can exploit that to arbitrarily constrain the agent’s behaviour. If the analogy holds, there’s then a class of environments for which AIXI, however finitely biased, is still optimally intelligent.
Yes. The no free lunch theorems are powerful in theory, but almost pointless in practice. I was hoping that AIXI could evade them, even in theory, but it seems to not be the case.
There’s another real point—focusing on your prior as “fit” to the problem/universe.
The space of possible priors Wolpert considered were very unlike our experience—basically imposing no topological smoothness on points—every point is a ball from the urn of possible balls. That’s just not the way it is. Choosing your prior, and exploiting the properties of your prior then becomes the way to advance.
Yet another application of David Wolpert’s No Free Lunch theorems.
https://en.wikipedia.org/wiki/No_free_lunch_theorem
NFL works with algorithms operating on finite problems. With algorithms operating on unbounded problems, you can benefit from Blum’s speedup theorem: for every algorithm and every computable measure of performance, there’s a second algorithm performing better than the first on almost all inputs.
I suspect here’s happening something similar: AIXI is finitely bias-able, and there are environments that can exploit that to arbitrarily constrain the agent’s behaviour. If the analogy holds, there’s then a class of environments for which AIXI, however finitely biased, is still optimally intelligent.
Yes. The no free lunch theorems are powerful in theory, but almost pointless in practice. I was hoping that AIXI could evade them, even in theory, but it seems to not be the case.
The point of the NFL theorems in practice is to keep you from getting your hopes up that you’ll get a free lunch.
So the point of no free lunch theorems is to tell you you won’t get a free lunch? ^_^
There’s another real point—focusing on your prior as “fit” to the problem/universe.
The space of possible priors Wolpert considered were very unlike our experience—basically imposing no topological smoothness on points—every point is a ball from the urn of possible balls. That’s just not the way it is. Choosing your prior, and exploiting the properties of your prior then becomes the way to advance.