Manipulating noise to get some data in right format and apply it to task using PPO

Question

Warning:
I understand that my question may seem strange, stupid, and impossible, but let's just think about this interesting problem. I would not ask a question like: how to create an AGI in google colab. This is a real problem and I believe that it is possible to solve it. My question may seem strange, because I have little experience and maybe I have indicated something wrong. But I assure you, this is not complete nonsense. My actual task is much harder then task bellow, therefore to simplify question i have simplified problem

I have RL task:
My environment is python, agent is usual RL agent(it takes action like others RL agents), but i have no list of actions. Goal is writing the fastest python code for sorting.
Policy net(network which returns action) returns me sorting string(something like: "[list1.pop(list1.index(min(list1))) for i in range(len(list1))]"), i execute it through "eval", get time of execution and use this time to form reward. But this task is easier, in my real task i have some variables and functions which model can use when produces sorting-strings. In our case it can be: "list_1", "some_function_which_helps_to_sort_list1_faster".

That's how i'm going to get sorting-strings:
I know for sure i need code model. When i was looking for it i found GPT-J. GPT-J is usual transformer Decoder only model. First of all i create random initial(it's constant) noise. Policy net also produces noise. At the first time this(noise from policy net) is random noise, but over the time model will be trained better and the noise that policy net will produce will already be meaningful and will help to get normal sorting-strings. I add first initial noise to noise which i got from policy net, pass it through GPT-J and finally get sorting string. I gonna train model with many different initial noises, because logically if initial noises are different, model will: 1) be trained better 2)produce new "the fastest" results. Entire approach looks like clip guided diffusion and i'm going to train it with PPO. As you remember, i have some variables that have to be in sorting strings. Therefore, there is a question: "How to make policy net to add these variables into sorting strings?". I believe reward forming will help to solve it.

How reward will be formed:
If policy net returns valid sorting string(which is valid python code and contains minimal set of variables i need(at least "list1") to pass it through eval without errors) but it is more slower than previous best sorting-string, reward will be tiny(0.1). If policy net returns valid sorting string which is faster than previous best sorting string, reward will be huge(1). If policy net returns invalid sorting string(which is not valid python code or doesn't contain minimal set of variables), reward will be negative(-1).

Thats how i'm going to train model. Bellow is how i'm going to use model at the inference time:
First of all set initial noise. Then make the same like in training loop, but don't save weights(weights will be updated according PPO, all steps, which were in "That's how i gonna get sorting-strings" will be executed, but when i get result from final iteration, i won't save this new weights which i get in inference time and if i need to surpass previous the best result, i will run inference loop with new initial noise till i surpass this result.)

What does here result from final iteration mean?:
That's exactly like in clip guided diffusion. I set some variable n_steps. For example it will be equal to 1000. Here i make 1000 calls to policy net, 1000 times update policy weights(if it's training time, at the inference time i also update weights but keep them in RAM memory and don't save)... And when i get final result at 1000th iteration, that means for me result from final iteration.

Question:
Is my approach of implementing this problem right? How would you implement my problem? If you have some helpful tips for me(maybe you have some links which will help me, may be i wrong form reward...; here i meant anything which might be helpful for me), don't hesitate to share it with me.

Answer 1

In terms of process optimization, RL is an excellent option but the environment definition and its policy could be difficult to implement.

That's why a genetic algorithm is a good alternative as it explores thousands of possibilities without having to define a complex environment or policy, overall if the environment is a conceptual one.

I don't know your process, but you can set all its potential sub-functions and assign them numeric weights (with any range) and the genetic algorithm would explore thousands of possibilities by modifying each weight randomly.

The result might not be so good as RL, but much better than a human thanks to the raw compute power.

PyGAD is a python library for Genetic Algorithm that can be applied to many cases: https://pygad.readthedocs.io/en/latest/

https://blog.paperspace.com/genetic-algorithm-applications-using-pygad/

Otherwise, there is a code to implement GA from scratch: https://machinelearningmastery.com/simple-genetic-algorithm-from-scratch-in-python/

Answer 2

From my understanding of your question, you are looking to implement a learning-to-sort algorithm.

There are current learning-to-sort machine learning solutions that do not require reinforcement learning. Reinforcement learning requires a lot of training data and code complexity that might not be necessary to create a working solution. For example, "The Case for a Learned Sorting Algorithm" by Kristo et al. uses the statistical regularities in the empirical Cumulative Distribution Function (CDF).

If you choose to use reinforcement learning, there has been success with using the Q-learning algorithm for learning-to-sort. Q-learning is easier to implement and debug than Proximal Policy Optimization (PPO).