acceptodds
Under review as a conference paper at ICLR 2027

Learning Behavioural Abstractions For Programmatic Policies

Abstract

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

Primary area:
reinforcement learning
Keywords:
Program Synthesis, Programmatic Policies, Behavioural Abstractions, Representation Learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_PZ81OpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents VIES (Video-Induced Exploration Space), a way to guide the search for programmatic game policies with behavior learned from gameplay videos. It builds on Bilevel Synthesis (Bi-S). In Bi-S, a local search over programs often finds many candidates with the same return, and a behavior target is used to choose among them. The behavior space in Bi-S is made of hand-designed game features. VIES replaces these features with a VQ video tokenizer trained on unlabeled gameplay videos, which describes each program's execution as a short sequence of discrete codes. This gives Bi-S the finite behavior space it needs, and it works with both DSL programs and LLM-written Python programs. In MicroRTS, the trained tokenizer finds programs that beat the opponent in almost all searches and gives the best self-play results. In Can't Stop, both the trained and the untrained tokenizer do better than the hand-designed features.

Critical strengths
  1. The idea is simple and fits Bi-S well. A VQ tokenizer gives the finite, factorized space the CMAB needs, and it works with both DSL mutation and LLM-written programs. On CombatMap, where the handcrafted features are all zero, both VIES variants still beat No guide, which is a good case for replacing hand-made features.

  2. The experiments are extensive and carefully designed. All conditions share the same search code, self-play results come with confidence intervals, and the opponent bot is kept out of the tokenizer data. The paper also reports where VIES loses.

Critical weaknesses
  1. It is unclear whether the gain comes from learning or from the discrete abstraction. An untrained tokenizer already gets much of the gain in MicroRTS and all of it in Can't Stop. There is no comparison with a simple non-learned summary, such as unit counts on the same grid, or with the features before quantization. Appendix A.8 also suggests that the acceptance rule is not very sensitive to similarity, so part of the LLM gap may come from accepting more ties.

  2. The MicroRTS results compare the methods only against one opponent and against each other. Best-response uses a single opponent, and success appears to mean winning one deterministic match, so the small differences from Handcrafted are not conclusive. Self-play win rates are measured only among the four conditions, so they say little about how strong the programs are in absolute terms.

Questions for authors
  1. Is Raw video computed on the same input as VIES, with repeated frames removed and 128 frames kept? Appendix A.3 says its padding differs from the tokenizer preprocessing. If the input is different, part of its poor result may come from the preprocessing rather than from the lack of a tokenizer.
  2. Which map do the LLM runs use? I could only infer workers 24x24 from Section 5.2.2. Do the found programs also win when playing as player 1?
2 comments
AuthorsOpenReview ↗

Response to Reviewer PZ81

Comment: It is unclear whether the gain comes from learning or from the discrete abstraction. An untrained tokenizer already gets much of the gain in MicroRTS and all of it in Can’t Stop. There is no comparison with a simple non-learned summary, such as unit counts on the same grid, or with the features before quantization.

Answer: Our comparison between Trained VIES and Untrained VIES isolates the effect of representation learning, since both conditions use the same architecture and quantization mechanism. The improvement of Trained VIES over Untrained VIES in MicroRTS demonstrates that learning contributes beyond discretization. We also compare against the handcrafted behavioural representations used in previous work, which include unit counts on the same grid, showing that VIES can outperform manually specified features. Finally, the bilevel search algorithm requires a discrete representation, as it treats the features as arms in a bandit problem, which makes it unclear how to use the features before quantization.


Comment: Appendix A.8 also suggests that the acceptance rule is not very sensitive to similarity, so part of the LLM gap may come from accepting more ties.

Answer: Thank you for giving us the chance to clarify this. We know that similarity plays an important role due to the large gap between VIES and No Guide. They both use Simulated Annealing, but the former uses similarity from our learned abstractions to break ties. VIES accepts more ties from the win-draw-lose metric, but it does so in a principled way, by choosing carefully which ties to accept based on the similarity metric.


Comment: The MicroRTS results compare the methods only against one opponent and against each other.

Answer: This is an important point, which we clarify in our revised version. The system using the handcrafted features was shown to defeat many other agents from the MicroRTS codebase (cf. Table 1 of Aleixo and Lelis, 2023). In our work, we show that our system with learned features can defeat this agent that was shown to defeat many others. This allowed us to focus on the research question of whether features learned from videos can be used to guide the process of synthesizing programmatic policies with a direct comparison to the system of Aleixo and Lelis. We added a paragraph, “Indirect Comparisons”, in Section 5.1 of the revised version to clarify this.


Question: Is Raw video computed on the same input as VIES, with repeated frames removed and 128 frames kept?

Answer: Good point about the pre-processing of the videos with the raw video baseline. We reran the raw video baseline with the same pre-processing used with VIES and have updated the plots in Figures 2 and 3. The results are qualitatively similar to our original submission, with raw video performing worse than the other systems we evaluated.


Question: Which map do the LLM runs use? I could only infer workers 24x24 from Section 5.2.2. Do the found programs also win when playing as player 1?

Answer: We used the Workers 24x24 map on the LLM-based experiments, and we had the synthesized programs play as player 0. We have not evaluated the programs as player 1, but we would expect a performance drop. In MicroRTS, a player's position on the map could influence the strategy required to win. Our choice of player 0 was arbitrary, and we expect the agent to perform well as player 1 if given the chance to learn to play in that position. We added a sentence to the "LLM-based synthesis" paragraph in Section 5.1 clarifying the map used and the position played.

Thank you for clarifying many of my questions, and I would keep my positive score.

Reviewer_nZaBOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes Video-Induced Exploration Space (VIES) that learns behavioral representations from execution videos to guide programmatic policy search. Specifically, a vector-quantized video encoder converts each execution into a sequence of discrete tokens. The resulting representation replaces handcrafted behavioral features in Bilevel Synthesis, providing targets and similarity scores for searching over programs. Experiments on MicroRTS and Can’t Stop environments show improvements over unguided search and sometimes handcrafted features.

Critical strengths
  1. Showcased the system is flexible for the representation, using both DSL-based synthesis and LLM-generated programs.
  2. Interesting finding that even an untrained quantizer can help with the performance and provide a short analysis.
Critical weaknesses
  1. The major weakness is the use of video is unmotivated here. Programs are already discrete and carry semantics information, why not directly quantize the program? why take the detour and render them to videos? Doesn't the program already specify the behaviors?
  2. Another weakness that there is no direct evidence showing the codebook actually learned reasonable abstractions.
  3. Lacks comparisons with other program synthesis baselines such as LLM-GS (which is already referenced in the paper).
  4. Only evaluated on simple, grid-world-like domains. This further limits the application of videos. Real-world videos have more visual nuances and would be hard to define a similarity metric / learn a code book as cleanly as in the grid world environment.
  5. Overall the contribution and scope feels limited.
Questions for authors
  1. What are the justifications of using videos here? What features do videos (specifically rendered from a generated program) have that the programs themselves do not? How generalizable do you think the results are? can it be applied to continuous tasks (e.g., gymnasium control tasks)? can it be applied to real world robotics tasks? and what are the reasonings?
  2. Do you have more direct evidence on the learned VIES corresponding to behavior abstractions? My understanding is that lines 419-426 is the closest, but those are not enough. R^2 around 0.2 is not very indicative. And saying the tokenizer are most associated with attack timing and spatial spread do not give a quantifiable evidence, it could just be those are the most important behaviors to solve the task.
10 comments
AuthorsOpenReview ↗

Response to Reviewer nZaB (1/2)

Comment: The major weakness is the use of video is unmotivated here.

Answer: We thank the reviewer for raising this question and giving us the opportunity to clarify our motivation. We consider the setting in which an agent learns behavioural abstractions by observing other agents acting in an environment, without access to their underlying implementations. This is analogous to learning by observing the behaviour of other agents, like humans and other animals do. We chose this setting because it allows the learner to learn abstractions from agents independently of how their policies are represented. Although learning abstractions directly from programs is a valid alternative, it requires access to the programs themselves, which we do not assume.


Comment: Another weakness that there is no direct evidence showing the codebook actually learned reasonable abstractions.

Answer: We have added several examples of abstractions learned by our agent in Section 5.3 of the revised version. Given a set of behaviours we selected, such as approaching the enemy based early in the game, we select a set of codes that predict such a behaviour. Such a simple approach can already reliably predict the behavior. Then, we showed how a non-linear probe can increase the prediction accuracy for a given behavior. Finally, we show that the nearest neighbours of a vector encoding a behaviours are much more likely to also encode the behaviour than a randomly selected video. The last study is important because it helps explain why the model learned can be effective in guiding the search. See Section 5.3 for the details.

These detailed results have certainly improved the quality of our work; thank you for suggesting this.


Comment: Lacks comparisons with other program synthesis baselines such as LLM-GS (which is already referenced in the paper).

Answer: We note that VIES and LLM-GS present orthogonal contributions. The former focuses on learning abstractions to help the search process, while the latter shows how an LLM can be used to synthesize programs. To demonstrate this, we implemented LLM-GS in the context of MicroRTS and compared its vanilla version with a version that uses VIES’ abstractions to guide the search.

The results are in Section 5.2.1 of the revised version. In short, without VIES, LLM-GS failed to find a best response in all runs attempted, due to the lack of search signal. Once we combined LLM-GS with VIES, we noted a substantial increase in the system's ability to find a solution. Thank you for suggesting this; this result demonstrates the generality of VIES.


Comment: Only evaluated on simple, grid-world-like domains. This further limits the application of videos. Real-world videos have more visual nuances and would be hard to define a similarity metric / learn a code book as cleanly as in the grid world environment.

Answer: Our problem domains are quite challenging, and offer great challenges to the current state-of-the-art in the synthesis of programmatic policies. For example, MicroRTS's action space grows exponentially with the number of units the player controls. The agent needs to respond in real time: 100 milliseconds per decision. Can’t stop is highly stochastic; both domains and adversarial, so the agent needs to reason about how the other agents are reasoning about the game.

Our paper presents advances in how to leverage videos to learn abstractions in these domains. We agree that moving to real-world robotic settings presents challenges that our work does not evaluate. Evaluating in such settings is beyond what we can afford in our small academic research lab. That said, we believe the lessons from our work could carry over to larger-scale experiments, but that remains to be proven.

AuthorsOpenReview ↗

Response to Reviewer nZaB (2/2)

Question: What are the justifications of using videos here?

Answer: We consider the setting in which the agent can only observe other agents acting; we don’t have access to the underlying program that encodes the policy.


Question: What features do videos (specifically rendered from a generated program) have that the programs themselves do not?

Answer: We consider the setting in which the agent doesn’t have access to other agents’ underlying programs.


Question: How generalizable do you think the results are? can it be applied to continuous tasks (e.g., gymnasium control tasks)?

Answer: We make no assumptions about the observation and action spaces. In principle, we could use VIES for continuous tasks as well. We do not know, however, how effective the method would be compared to baselines. VIES works best when the underlying problem has visual features that appear with no clear reward signal. The vision model can capture these features, and the bilevel search can learn their importance.


Question: can it be applied to real world robotics tasks? and what are the reasonings?

Answer: We also believe it could be applied to real-world robotics. However, we would need to scale the model size, the amount of data, and thus the compute. We would need more data because the real world is noisier and would require more data to learn what is important and what can be ignored.


Question: Do you have more direct evidence on the learned VIES corresponding to behavior abstractions?

Answer: We have added a whole section to the paper with examples of what is learned in the codebook; see Section 5.3 of the revised paper. We present different experiments quantifying the evidence that different codes are associated with a given abstraction. Namely, we consider simple rules that verify whether a given code is at a given position; we trained a non-linear probe on the discrete representation, and we study the neighbour videos of a video with a given behaviour, to study the smoothness of the learned space, which could be important for the search. Adding this section to the paper has substantially improved its quality. Thank you for suggesting it!

Reviewer_nZaBOpenReview ↗

Response to the Authors (1/2)

I thank the authors for the detailed response.

I can understand the comparison with LLM-GS now. So I consider that original concern to be resolved.

However, none of my critical concerns are sufficiently resolved: 1) the use of video is unmotivated; 2) the behavior abstraction evidence is weak; and 3) it is only evaluated on simple environments and broad generalization is questionable.

 

The use of video is unmotivated

We consider the setting in which an agent learns behavioural abstractions by observing other agents acting in an environment, without access to their underlying implementations.

We chose this setting because it allows the learner to learn abstractions from agents independently of how their policies are represented.

We consider the setting in which the agent can only observe other agents acting; we don't have access to the underlying program that encodes the policy.

My understanding is that VIES has two stages:

  1. Offline representation learning: Videos of existing agents are used to train a tokenizer that maps execution trajectories into discrete representations.
  2. Program synthesis: Candidate programs are generated, executed, and their rendered videos are encoded using the pretrained tokenizer to provide a behavioral similarity signal for guiding search.

I understand the authors' argument that the first stage does not assume access to the source programs of other agents. However, the second stage explicitly generates and executes candidate programs (Figure 1). Therefore, the programs being optimized are available during synthesis. So, it does not explain why rendered videos are the appropriate representation for program synthesis.

For example, given an execution trajectory, the behavioral representation could potentially be learned directly from sequences of environment states and actions, without rendering them as videos. Such a method would also be independent of the source programs of other agents. Likewise, since the candidate programs are accessible during synthesis, learning behavioral representations from their program structures or execution traces is also a possible alternative.

Furthermore, learning representations from observations of other agents has much prior work (e.g., Aytar et al. (2018) Playing Hard Exploration Games by Watching YouTube; Sermanet et al. (2018) Time-Contrastive Networks). These works already explore learning representations from videos of other agents and using them to guide policy learning. This makes it even more important to clarify what the video-based representation contributes specifically to program synthesis.

 

The behavior abstraction evidence is weak

The new section 5.3 has several issues:

  1. The behaviors are predefined instead of discovered. The existing 5.3 is a post-hoc analysis demonstrating that predefined behavioral information can be recovered from the learned representation. This does not show that meaningful behavioral abstractions emerged during representation learning. A representation that preserves sufficient information about the original video could also support such predictions, without necessarily organizing the execution trajectories into distinct behavioral abstractions.
  2. There is no trained-vs-untrained comparison. This is particularly important because one of the interesting findings of the paper is that an untrained quantizer can already provide substantial improvements in program synthesis. So it could be that an untrained quantizer already captures all of these abstractions.
  3. Behavioral correlations do not mean evidence of distinct abstractions. The reported AUCs are encouraging, but they do not establish that the model has learned distinct behavioral concepts. For example, early attacks, heavy-unit movement, and unit production may correlate with broader properties such as game progression, unit composition, or winning outcomes.

Directly examining the patterns or clusters emerging from the learned representation, without first specifying the behaviors to search for, would provide more convincing evidence of emergent behavioral abstractions.

Reviewer_x9PnOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies programmatic policy search in the MicroRTS and Can’t Stop environments. The paper starts with a bilevel search algorithm, Bi-S, that searches for policies in behavioral and program space. Bi-S uses handcrafted variables to encode trajectories into discrete space. Instead, this work learns a VQ-VAE from pre-collected data to replace the handcrafted feature mapping. In the experiments, the proposed method outperformed the handcrafted baseline.

Critical strengths

The method finds a better way to model policy behavior and design a search algorithm to use it. A learned behavior representation can encode more information than handcrafted feature rules.

Critical weaknesses

The method is evaluated on MicroRTS and Can’t Stop, but the results suggest that training the VQ-VAE is effective only on MicroRTS. The root causes of the phenomenon are unclear.

Questions for authors
  1. In Figure 4, if you use search time as the search budget, you need to provide information about the machine, such as the CPU and GPU settings. Otherwise, none of the reviewers can evaluate the result. It would be better to use the number of programs synthesized.
  2. In Figure 2, although you state that 1 USD equals 800 programs, it would be better to use aligned axis labels.
  3. In Figure 1, you try to use tic-tac-toe to illustrate your method; you should tell the reader what the number means. Is it the number of quantizations used in VQ-VAE? Also, what will the program look like in a tic-tac-toe environment?
  4. In Figure 5, the Don’t Stop cannot benefit from training. I would like to know whether this is due to the environment's randomness, the quality of the training data, or something else.
2 comments
AuthorsOpenReview ↗

Response to Reviewer x9Pn

Comment: The method is evaluated on MicroRTS and Can’t Stop, but the results suggest that training the VQ-VAE is effective only on MicroRTS. The root causes of the phenomenon are unclear.

Answer: We conjecture that training does not help on Can’t Stop because of the game's stochastic nature. The underlying model cannot predict specific dice outcomes and instead converges to the game's average outcome, resulting in a representation that isn’t superior to the untrained one. Designing architectures that can handle stochastic environments is an interesting direction for future research. We added the text above to the end of Section 5.2.2 to clarify this limitation.

Importantly, our untrained model already performs better than the baselines, and we explain why: the untrained model partitions the space well enough that the learning algorithm can associate the untrained features with successful outcomes.


Comment: In Figure 4, if you use search time as the search budget, you need to provide information about the machine, such as the CPU and GPU settings. Otherwise, none of the reviewers can evaluate the result. It would be better to use the number of programs synthesized.

Answer: We added the following to Section 5.1 of the revised version:

We trained the model as a pre-processing step on an NVIDIA L40S GPU. Once trained, the experiments were conducted on Intel Xeon Gold 6448Y CPUs with a 2.10 GHz frequency.

We have replaced the plots in Figure 4 with plots whose x-axes show the number of programs synthesized.


Comment: In Figure 2, although you state that 1 USD equals 800 programs, it would be better to use aligned axis labels.

Answer: We replaced the Gemini plot with one whose x-axis also shows the number of programs generated, to match the GPT-OSS plot.


Comment: In Figure 1, you try to use tic-tac-toe to illustrate your method; you should tell the reader what the number means. Is it the number of quantizations used in VQ-VAE? Also, what will the program look like in a tic-tac-toe environment?

Answer: We used tic-tac-toe for illustration purposes only. Using our approach to learn programs to play tic-tac-toe would be overkill, as current models can easily generate solutions that can force a draw in the game. To avoid confusion, we replaced the tic-tac-toe drawings with a representation of the Earth to represent the environment more broadly. The vectors are arbitrary and meant to illustrate the computation behind the approach. We added a sentence to the caption of Figure 1 in the revised version:

The numbers in the vectors are arbitrary and were chosen to illustrate the computation of VIES.


Question: In Figure 5, the Don’t Stop cannot benefit from training. I would like to know whether this is due to the environment’s randomness, the quality of the training data, or something else.

Answer: This is a good question, for which we added a conjecture to the paper (see our first answer for details).

Thanks for your response. You suggest that the main reason VIES cannot achieve better results in Can’t Stop is that it can't handle the environment's randomness. I will not raise my score because this is still a conjecture and cannot be proven or disproven.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Comment

We thank all reviewers for their time and insightful comments. We reply in detail to each reviewer below. Here we summarize the main changes in the revised version of the paper, where all modifications are highlighted in blue.

Changes following Reviewer x9Pn

  • Clarified why VIES with a trained model does not improve performance on Can't Stop.
  • Added information on the hardware used in the experiments.
  • Replaced the plots in Figures 2 and 4 so that they use the number of programs generated as the x-axis.
  • Updated Figure 1.

Changes following Reviewer nZaB

  • Clarified our motivation for using videos.
  • Added a detailed analysis of the behavioural abstractions the system learns.
  • Added experiments showing that VIES can be used to improve LLM-GS.

Changes following Reviewer PZ81

  • Reran the experiments with the Raw-Video baseline to ensure the same pre-processing is used for VIES and the baseline.
  • Added several important clarifications throughout the paper.

The paper has improved significantly thanks to the reviewers' comments. We would be happy to answer any follow-up questions during the discussion period.

Dear Reviewers,

Please take a moment to review the authors' responses and participate in the discussion, particularly if you have any outstanding questions or concerns. We also encourage you to update your assessments, if appropriate, in light of the authors' responses and the ongoing discussion.

Your feedback is greatly appreciated and will be valuable in helping us reach a fair and well-informed final decision.

Thank you for your time and contributions!

Best regards, AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.