You cannot RL learn an O(N) algorithm in an O(1) feed forward neural network. You could RL learn that when someone specifies a number, the appropriate thing to

You cannot RL learn an O(N) algorithm in an O(1) feed forward neural network. You could RL learn that when someone specifies a number, the appropriate thing to say is "Ok, 40 asterisks, let's count them, 1, *, 2, *, 3 , *, ..." and then it would indeed produce 40 asterisks. But not as a single string. Because producing them as a single contiguous string requires some offline state/memory/processing, and all the neural network has access to is the last ~page of text. Embedding the counting process into the text itself kind of embeds the state of the O(N) algorithm in the O(N) text itself, that is, "unrolling the loop" externally.