Stopping criteria for episodic yet "continuous" optimization tasks?

Question

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:

1. iterations - see what the best improvement is after applying k rewrite rules

2. feasibility - terminate after some cumulative reward threshold has been reached (ex. 50% of the tree is reduced), of course not guaranteed for every input

3. n errors - terminate after n negative improvements have been observed

4. 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?

Answer 1

A practical approach to take while training your model might be:

1. Set a maximum number of iterations before the episode ends, some value that's probably more than sufficient to achieve an optimal solution.
2. Let the agent terminate the episode at any point in time.
3. Add a small negative reward at every point in time.

This should encourage the agent to terminate the episode as soon as it can't make sufficient progress to outweigh the small penalty, without picking any hard limit.

At test time:

You can go with a simulated annealing approach: Introduce a temperature variable $T$ which decays from some initial value down to 0. Whenever the agent picks a rewrite rule, apply it with probability 1 if it's an improvement, and $\exp(s/T)$ otherwise, where $s$ is how much worse the solution got. Otherwise ignore the rewrite and resample from the agent policy (if it's a deterministic policy, you could add noise somehow). If the agent decides to terminate the episode, ignore it (that was a helpful heuristic for training, but needn't be applied here).