A couple of immediate issues with the algorithm side of things:
First, there are 2n possible programs with length n. Your ‘find a better algorithm and iterate’ canget caught in sequences like this:
Program, generation 1: for (uint128_t i = 0; i < 0xFFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFF; i++) {nop();} do_the thing();
Program, generation 2: for (uint128_t i = 0; i < 0xFFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFE; i++) {nop();} do_the thing();
Program, generation 3: for (uint128_t i = 0; i < 0xFFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFD; i++) {nop();} do_the thing();
Program, generation 4: for (uint128_t i = 0; i < 0xFFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFC; i++) {nop();} do_the thing();
Etc. Forward progress is not enough here.
(I know that you can’t actually iterate to 2128 and actually get a result in any sane amount of time. Replace the loop with anything else that’s a nop in practice but ever-so-slightly reduces your chosen metric.)
Second, what do you do when the optimizer returns no strictly-better agent, and the evolutionary algorithm is in a local minima? Just because it will get better ‘eventually’ doesn’t mean it’s going to find something better within the heat death of the universe.
Third: how do you find unseen games? Either you require O(total tested algorithms) games, or you repeat unseen games. If you repeat unseen games there’s a chance—and I would argue a significant chance—that you stumble across something that happens to solve the unseen games you ran this time but is not actually general. Then you get stuck.
Fourth: even assuming the loop works, you have no guarantee that the loop will get faster over time. Solving some games faster != improving itself faster.
=====
In general: any time you have an argument for why something will work that works equally well for Levin Search, you don’t have a good argument. (Why Levin search? Because it is has theoretically optimal runtime complexity for many classes of problems… and yet is utterly impractical in practice.)
This algorithm won’t get caught in a loop like the one you mentioned, because it uses the same process as the one described in the AutoML-Zero paper. In the article, they ‘found a better algorithm and iterated’ without any problem whatsoever, using the processes described in figures 1 and 2. Please check the paper for that.
About your second point: that’s exactly the aim of the experiment, to know if a strictly-better agent can be found with an automatic process. If we don’t get there using substantial computation within an acceptable amount of time, then the experiment will have failed. But, as with all experiments, there’s good reasons try.
Third: how do you find unseen games? Simply, unseen games are just games for which the algorithm hasn’t been training to perform well at. In this experiment, this would be experiments that are not on the Deepmind MuZero benchmark. Obviously, these unseen games will be changed in every cycle (every point 5).
Fourth: Yes, of course there’s no guarantee, because that’s also the point of the experiment. To know if this will happen. And again, there’s good reason to think so. Here’s the explanation again: you use a machine learning technique to find a general learning program that performs better than MuZero. But MuZero in itself is a deep reinforcement learning program that’s designed to quickly learn many different games. And what is a game? An objective based activity related to certain rules. Hence, if the new program performs better than MuZero as a GLA, then it would be logical to assume that it will perform better as well in the process of finding better GLAs, because finding GLAs is a “game” too. This is also explained in points 5 and 6.
About your ‘in general’ statement, at no point I am presenting an argument saying that these new algorithms will perform better or equally well than Levin Search. What I propose with this experiment is to automatically find improved versions of the general learning algorithms that we currently have. The ideal endpoint of the experiment would be to automatically find algorithms that are CLOSE to the best possible (such as Levin Search) but are practically feasible.
A couple of immediate issues with the algorithm side of things:
First, there are 2n possible programs with length n. Your ‘find a better algorithm and iterate’ can get caught in sequences like this:
Program, generation 1:
for (uint128_t i = 0; i < 0xFFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFF; i++) {nop();}
do_the thing();
Program, generation 2:
for (uint128_t i = 0; i < 0xFFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFE; i++) {nop();}
do_the thing();
Program, generation 3:
for (uint128_t i = 0; i < 0xFFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFD; i++) {nop();}
do_the thing();
Program, generation 4:
for (uint128_t i = 0; i < 0xFFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFF_FFFC; i++) {nop();}
do_the thing();
Etc. Forward progress is not enough here.
(I know that you can’t actually iterate to 2128 and actually get a result in any sane amount of time. Replace the loop with anything else that’s a nop in practice but ever-so-slightly reduces your chosen metric.)
Second, what do you do when the optimizer returns no strictly-better agent, and the evolutionary algorithm is in a local minima? Just because it will get better ‘eventually’ doesn’t mean it’s going to find something better within the heat death of the universe.
Third: how do you find unseen games? Either you require O(total tested algorithms) games, or you repeat unseen games. If you repeat unseen games there’s a chance—and I would argue a significant chance—that you stumble across something that happens to solve the unseen games you ran this time but is not actually general. Then you get stuck.
Fourth: even assuming the loop works, you have no guarantee that the loop will get faster over time. Solving some games faster != improving itself faster.
=====
In general: any time you have an argument for why something will work that works equally well for Levin Search, you don’t have a good argument. (Why Levin search? Because it is has theoretically optimal runtime complexity for many classes of problems… and yet is utterly impractical in practice.)
Hey! Thanks for your comment.
This algorithm won’t get caught in a loop like the one you mentioned, because it uses the same process as the one described in the AutoML-Zero paper. In the article, they ‘found a better algorithm and iterated’ without any problem whatsoever, using the processes described in figures 1 and 2. Please check the paper for that.
About your second point: that’s exactly the aim of the experiment, to know if a strictly-better agent can be found with an automatic process. If we don’t get there using substantial computation within an acceptable amount of time, then the experiment will have failed. But, as with all experiments, there’s good reasons try.
Third: how do you find unseen games? Simply, unseen games are just games for which the algorithm hasn’t been training to perform well at. In this experiment, this would be experiments that are not on the Deepmind MuZero benchmark. Obviously, these unseen games will be changed in every cycle (every point 5).
Fourth: Yes, of course there’s no guarantee, because that’s also the point of the experiment. To know if this will happen. And again, there’s good reason to think so. Here’s the explanation again: you use a machine learning technique to find a general learning program that performs better than MuZero. But MuZero in itself is a deep reinforcement learning program that’s designed to quickly learn many different games. And what is a game? An objective based activity related to certain rules. Hence, if the new program performs better than MuZero as a GLA, then it would be logical to assume that it will perform better as well in the process of finding better GLAs, because finding GLAs is a “game” too. This is also explained in points 5 and 6.
About your ‘in general’ statement, at no point I am presenting an argument saying that these new algorithms will perform better or equally well than Levin Search. What I propose with this experiment is to automatically find improved versions of the general learning algorithms that we currently have. The ideal endpoint of the experiment would be to automatically find algorithms that are CLOSE to the best possible (such as Levin Search) but are practically feasible.
Kind Regards