Right, but what would be the difference if this program was produced by Deep RL algorithm, where the state is the current program (an encoding of the program) a

Right, but what would be the difference if this program was produced by Deep RL algorithm, where the state is the current program (an encoding of the program) and the actions are valid instructions in your stack language? An episode in this case is an iterative call to the Deep RL system until it outputs <STOP> at which step you give it a reward (negative number of collisions say), and before that you can send the actions to your stack machine. Once you're satisfied with the final number, just concatenate all the produced actions to get your final program. I just don't see a fundamental difference, especially once you start doing things like Asynchronous Actor-Critic et al. And then you can start doing Monte Carlo Tree Search on top of that since you have a simulator available...