The selected multi-step algorithms to evaluate the performance of the different single-step models are MCTS [1]}, which dynamically assesses the state values of the search tree at run-time, and Retro* [2]}, which instead uses an A* path finding algorithm in combination with an oracle function.
In the case of Retro*, we refrain from using the oracle function and rely only on the priors of the single-step model for initial cost estimation, given that the original oracle function is generally shown to have little impact [3]} and is trained on USPTO data, which could cause information leakage. We defer from using a self-play algorithm since it would be necessary to retrain the self-play algorithm per problem instance, i.e., the set of used building blocks.
