EliteTable: Self-Improving Program Search for Executable Control Policies

EliteTable is a self-improving program-search algorithm that leverages large language models (LLMs) to enhance its performance. It operates using a fixed-capacity table that contains high-scoring solutions, which guide the generation of new proposals, modifications of existing solutions, and combinations of multiple solutions. The algorithm’s effectiveness was tested across six Gymnasium control tasks, with each task undergoing ten generations and accommodating fifty candidate slots per generation. Each task was assessed through ten independently initialized searches. Results indicated that candidate-score medians improved from the first to the final generations in all six tasks, while selected-winner search-score medians increased in five of the tasks. Notably, in the CartPole-v1 task, the selected winner achieved the maximum search score during the first generation across all ten searches. Furthermore, all ten paired held-out endpoints showed improvement in four out of the six tasks. Although BipedalWalker-v3 and CarRacing-v3 demonstrated improvements, they did not meet their reporting targets. Conversely, six out of ten searches for Acrobot-v1 experienced declines in held-out episodes, resulting in a negative median paired change. These findings highlight the advancements made during the program search and the successful transfer of selected-winner gains to new episodes in certain tasks. Further comparisons and ablation studies are necessary to determine EliteTable’s relative performance and the specific contributions of its components.

Source: arxiv.org