The task I have consists of applying a selection of "rewrite rules" to some given input in some order in to minimize some property of the input. For example, let us say the input is a tree representing some structured information, we wish to decrease the size of the tree while still preserving most of the info.
For this task, assume all the rewrite rules occur at global scale and always result in a valid solution.
I am trying to frame this task as a reinforcement learning task where each "episode" is an agent applying said rewrite rules such a given input (the environment in this case). At each step, the agent chooses a rewrite rule to apply and receives a reward that is proportional to the improvement (positive or negative) that rewrite rule had on the input in minimizing that property. Such improvement is measured by some cost function C.
The perhaps obvious trouble with this setup is that is not clear when to stop applying rewrite rules. The environment doesn't have a clear idea of when to terminate. The environment is episodic but the episodes are "continuous" or possibly even infinite on paper as in theory it is possible to apply an infinite number of rewrite rules to the same input.
Stopping at first sign of a negative improvement is likely to be greedy and naive as there might be positive improvements to be had after some number of improvements, but again this isn't guaranteed either.
Some other possible ideas I have thought about, mostly from traditional optimization areas are:
iterations - see what the best improvement is after applying k rewrite rules
feasibility - terminate after some cumulative reward threshold has been reached (ex. 50% of the tree is reduced), of course not guaranteed for every input
n errors - terminate after n negative improvements have been observed
n errors in a row - terminate after n negative improvements in a row
All of these feel half-baked for the task at hand, would anyone be able to point to something that is more (hopefully theoretically) fitting?