Learning Behavioural Abstractions For Programmatic Policies

Synthesizing a programmatic policy is a search problem over a discrete, non-smooth space. Small changes to a program can produce large changes in its behaviour and return. In practice, the resulting optimization landscape tends to be flat, making it difficult to know where to search next. Existing approaches provide search guid- ance through domain-specific, handcrafted behavioural features, which limit which behaviours the search can explicitly target to those their designer chose to describe. We introduce VIES (Video-Induced Exploration Space), a method that turns execu- tion trajectories in the form of videos into a discrete behaviour abstraction space. From unlabelled videos of agents acting in the environment, a vector-quantized model maps executions to short sequences of discrete symbols. These symbols form a finite, factorized behavioural abstraction that can guide search when the task outcome cannot distinguish candidates, replacing behavioural features that otherwise have to be designed by hand for each domain. The representation is independent of how candidate programs are constructed: we use the same learned behavioural signal to guide synthesis over both a domain-specific language and LLM-written Python. We evaluate the approach on MicroRTS and Can’t Stop, across best-response and self-play settings. Comparing conditions with and without the discrete abstractions shows that access to the trajectory alone is not enough: guidance from raw videos captures little of the benefit provided by the discrete abstraction. Surprisingly, even an untrained quantizer can be helpful, while training organizes the resulting space around more meaningful visual, behavioural, and outcome-related structure. Together, these results show that execution traces in the form of video can provide the behavioural structure needed to navigate otherwise flat program spaces without requiring that structure to be specified by hand