3
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ It sounds to me more like a framing problem, but I could be wrong. I don't see why RL agent is used together with GPT-J: They are 2 very different things. However, it could be a great idea. Maybe you could edit your question with an example? There are plenty of ways to do fast sorting, but I'd like to know what kind of sorting it is? (alphabetical, category, date, ...) $\endgroup$ Jun 26 at 19:56
  • $\begingroup$ @Nicolas Martin, I have a real problem from the financial sector that is solved in the same way as the sorting problem that I described. Therefore, I gave an example with sorting, to make it easier and clearer. I am satisfied with any type of sorting and in general it is not particularly important for me, because this is not my real task. But for simplicity, let's assume that we are dealing with alphabetical sorting. $\endgroup$ Jun 28 at 7:41
  • $\begingroup$ At the expense of the examples that you asked to add, I don’t even know how to explain what I described in more detail. It seemed to me that I described each step. What comes from where and what goes where. Can you tell me exactly what you don't understand? $\endgroup$ Jun 28 at 7:42
  • $\begingroup$ In some researches usual deep learning and RL were used together arxiv.org/abs/2009.01325 $\endgroup$ Jun 28 at 7:44
  • $\begingroup$ I myself forgot some of the points described in the question. Been asking a question for a long time. But the idea of combining GPT-J and RL Agent is as follows: RL agent does not return a specific action from the list (there are simply no actions), it returns a vector (something like last hidden state). I also create another vector of the same dimension (random), they are combined and fed into GPT-J. Then, in the learning process, the weights of the RL agent are changed so that rows with sorting are better generated (check "How reward will be formed:") $\endgroup$ Jun 28 at 8:04

2 Answers 2

1
+100
$\begingroup$

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/

$\endgroup$
2
  • $\begingroup$ Thank you, i'm going to accept answer after bounty expiration. Want to see other answers. $\endgroup$ Jun 29 at 9:34
  • $\begingroup$ You're welcome. Hopefully, there are other ones because it is a very interesting problem. $\endgroup$ Jun 29 at 9:36
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.