Language Models Speed Up Local Search for Finding Programmatic Policies
Authors: Quazi Asif Sadmine
Hendrik Baier
Levi Lelis
Venue: Accepted by TMLR ()

Abstract: Encoding policies that solve sequential decision-making problems as programs offers advantages over neural representations, such as interpretability and modifiability of the policies. On the downside, programmatic policies are elusive because their generation requires one to search in spaces of programs that are often discontinuous. In this paper, we leverage the ability of large language models (LLMs) to write computer programs to speed up the synthesis of programmatic policies. We use an LLM to provide initial candidates for the policy, which are then improved by local search. Empirical results in three problems that are challenging for programmatic representations show that LLMs can speed up local search and facilitate the synthesis of policies. We conjecture that LLMs are effective in this setting because we give them access to the outcomes of the policies rollouts. That way, LLMs can try policies encoding different behaviors, once they observe what a previous policy has accomplished. This process forces the search to explore different parts of the space through "exploratory initial programs". Experiments also show that much of the knowledge LLMs leverage comes from the domain-specific language that defines the search space - the overall performance of the system drops sharply if we change the name of the functions used in the language to meaningless names. Since our system only queries the LLM in the first step of the search, it offers an economical method for using LLMs to guide the synthesis of policies.

Published in Transactions on Machine Learning Research (11/2024)
Language Models Speed Up Local Search for Finding Programmatic Policies
Quazi Asif Sadmine
sadmine@hualbetta.cm
Amii, Department of Computing Science University of Alberta
Hendrik Baier
A.j.s.biierBtue.coo
Eindhoven University of Technology
Levi H. S. Lelis
levi. Tni.lelis@huaberta..o ca
Amii, Department of Computing Science University of Alberta
Reviewed on OpenReview: https: // openreview. net/ forum? id= 1Bky2I1mJY
Abstract
Encoding policies that solve sequential decision makiig problems as programs offers advan- tages over neural representations, such as interpretability and modifiability of the policics. On the downside, programmatic policies are elusive because their generation requires one to search in spaces of programs that are often discontinuous, In this paper, we leverage the ability of large language models (LLMss) to write computer programs to speed up the synthesis of programmatic policies. We policy, which are then improved by local search. Empirical results in three problems that are challenging for programmatic representations show that LLMs can speed up local search and facilitate the synthesis of policies. We conjecture that LLMs are effective in this set- ling because we give them access the outcomes of the policies rollouts. That way, LLMs can try policies encoding different behaviors, once they observe what previous policy has accomplished. This process forces the search explore different parts of the space through "exploratory initial programs". Experiments also show that much of the knowledge LLMs leverage comes from the domain-specift language that defines the search space the overall performance of the system drops sharply if we change the name of the functions used in the language to meaningless names. Since our system only queries the LLM in the first step of the search, offers an economical method for using LLMs to guide the synthesis of policies.
LLM to provide initial candidates for the
1
Introduction
There is a growing interest in using programmatic representations to encode solutions to sequential decision-
making problems (oontt et al. 2010 Aguas et al.] 2018 Bastani et al., 2018 Trivedi et al. 2021
Moraes
ct al.
2023
Liang et al.] 20233 Depending on the language used, programs that encode programmatic
solutions can generalize to unseen scenarios better than neural representations (Inala et. al.
2020 Trivedi
et al.
2021
Such solutions can also be interpretable (Verma et al.) 2018a Medeiros et al. 2022
Aleixo &
Lelis
2023
which could allow users to manually modify computer-generate solutions.
The challenge of using programmatic representations is that one needs to search in large and discontinuous spaces of programs, typically defined by a Noomain-speciie language. In the context of supervised learning,
a common approach to finding programmatic solutions is learn function that guides the scarch in the
programmatic space (Balog al.) 2017 Odena et al.) 2021 Odena & Sutton 2020: Fijalkow al.) 2022; Ameen & Lelis 2023). This function is learned in self-supervised manner by exploiting the structure of

---

Published in Transactions on Machine Learning Research (11/2024)
the language. For example, in program synthesis, one is given a set of input-output pairs and must find program that maps every input to its output. A guiding function can be learned by generating a set of random programs from the language. Training problems can be created by providing random input values to these programs, which produce the target outputs. The guiding function is trained to solve the problems represented by the input-oulputs pairs whose solution is the program that was randomly generated.
However, it is unclear how to generalize this self-supervised approach to learning guiding functions to solve sequential decision-making problems, where the agent learns by interacting with the environment. This is because, in many settings, the agent does not know the problem it will attempt to solve prior to learning, making it difficult to learn a guiding function as is done in the supervised learning setting. Instead of attempting to learn a guiding function, in this paper, we present a system that leverages the ability of large language models (LLM) to write computer programs encoding "general knowledge" to guide the search for programmatic policies. The type of guidance that we will explore is through the initialization of the search for a program encoding a policy to solve the problem. Similarly to how weight initialization plays an important role in training neural networks (Glorot & Bengio 2010 LeCun et al. 2012), we show that LLM can also play an important role in initializing the learning process of programmatic policies.
A common approach to synthesizing programmatic policies is to use stochastic local search algorithms to search in syntax-based [Koza 1992: Carvalho et al. 2024 or semantic-based (Moraes & Telis) 2024 spaces of programs. The system we introduce in this paper, Local Search with LLM (LS-LLM), proposes a novel integration of an LLM into local search to speed up this process. We hypothesized that an LLM can guide the search for policies by initializing the search in promising parts of the space.
We evaluated our hypothesis three deterministic domains that are challenging for current systems that generale programmatic policies: Poachers & Rangers (PR) and Climbing Monkey (CM) (Moraes et al., 2023), and MicroRTS (Ontañón 2013). LS-LLM was more sample efficient than the evaluated baselines, including a system that is identical to LS-LLM but does not use an LLM to initialize the search. We also show that LS-LLM's performance drops sharply once we encrypt the name of the functions and terminal symbols used the domain-specific language, suggesting that the knowledge the LLM leverages largely comes from interpreting those names. Our results suggest that LLMs can be an economical and effective solution in guiding local scarch algorithms in synthesizing programmatic policies [
2 Problem Definition
Let (S, (,,,,))),),)))) be a Markov decision process (MDP). Here, S is the set of states, and A is the set of actions. The function p(s+41/s; a,) encodes the transition function, which returns the probability of reaching 8t+1 given that the agent is 8y and chooses ag. The agent observes a reward value RM+1, which is given by a function r, when moving from st to 81+1- j is the distribution of initial states of the MDP and y in [o, 1] is the discount factor. A policy is function that receives a state s and an action a and returns the probability in which a is chosen in s. A solution to an MDP is policy that maximizes the expected sum of discounted rewards for starting at 8p ~ μr R - Er 1 Re+1).
We consider policies encoded in programs written in domain-specific language (DSL). The set of programs that a DSL accepts defines the set of policics that the agent can consider. This programmatic policy space is defined as a context-free grammar (M,2, W, I), where M, Ω W, and S are the sets of non-terminals, terminals, the production rules of the grammar, and the grammar's initial symbol, respectively. Figure [ shows an example of a DSL, where M = [1, C, s = {ci, e2 b2 b2, if, then), W are the production rules (e.g.. C CCCC),, and I is the initial symbol.
We represent programs as abstract syntax trees (AST), where each node and its children represent production rule if n represents non-terminal symbol. For example, the root of the tree in Figure D which represents the non-terminal I, and its children correspond to the production rule I + if( then C. Leaf nodes are terminals. Figure D shows an example of an AST for "if by then a ez A DSL D defines the possibly infinite space of programs [D]: in our case, cach in [D] represents a policy. Given such a space,
The source code used run the experiments of this paper available online: http:://gttubb.co//aaaaaaaaatat
2

---

Published in Transactions on Machine Learning Research (11/2024)
if
B
then
C
1 + if(B) then C
C CC ci 02
C
C
B b b2
CI
Figure 1: Abstract syntax tree for "if by then ei o2" and the language in which the program is written.
we need to find a policy that approximates a solution to maX Ex... Ex R R We use local
search algorithm find an approximate solution this optimization problem (Carvalho al, 2024
3 Programmatic Policy Learning as Local Search
Previous work showed that a simple implementation of stochastic hill-climbing (SHC) achieves state-of-the- art results in challenging domains (Carvalho al.) 2024; Moraes & Lelis] 2024), so this is what use in our experiments. SHC starts with arbitrary policy ' a candidate that maximizes the agent's return.
The initial candidate is generated starting with the initial symbol 7 and applying production rule to replace I; the rule is chosen uniformly at random or according to a probability distribution, if one is available [Trieedi et al. 2021). ). We replace the leftmost non-terminal X of the resulting string with the symbols on the right- hand side of a production rule for X; the rule is randomly chosen among those for X. This process continues until a string with only terminal symbols is generated, which represents the scarch's initial candidate.
SHC searches in the space defined by both the DSL and neighborhood function N₂ (TT) This function receives candidate and returns set of k policies the neighbors of π in the search space. SHC evaluates all k neighbors in terms of an estimate of the return R of each neighbor; SHC selects the neighbor of æ with the largest estimated value R. The value of is estimated by rolling out each of the neighboring policies. This process is repeated with the newly selected candidate policy. SHC stops none of the neighbors has an estimated R-value that is larger than the current candidato; the search reaches a local optimum. We implement SHC with a restarting strategy: once SHC reaches a local optimum, we restart the search from a randomly chosen initial candidate. SHC with restarts returns the best solution encountered in all searches.
SHC is stochastic because the generation of the initial candidate and the neighborhood function are stochas- tic. In non non-deeermiiistic environments, we can only approximate the values of R when deciding which neighbor to select. The neighbors N& returns are generated as follows. Each of the & neighbors is generated by randomly choosing a node n in the AST the program π that represents a non-terminal symbol (e.g., the nodes I, B or in Figure 7) and replacing the sub-tree rooted at n with a randomly generated sub-tree. This new sub-tree is generated by following the same process described generate the initial candidate, The difference is that we start by replacing the non-terminal of node n, instead of the initial symbol I.
4 Local Search with LLM (LS-LLM)
Local Search with LLM (LS-LLM) is described in Algorithm 1 and a schematic view of it is shown in Figure 2 It receives the MDP P, large language model M, budget B that specifies the number of model queries that are allowed, domain-specific language D, and local search algorithm, SHC in our implemennation.. LS-LLM returns an approximate solution to P. Figure 2 shows which code lines in Algorithm interact with the MDP (first column), the LLM (second column), and SHC (third column).
LS-LLM leverages the ability of the LLM to encode common knowledge from training data, including the ability to generate computer programs, speed up the search for programmatic policies. LS-LLM first requests from the LLM set of policies that solve the MDP, for which a textual description provided
3

---

Published in Transactions on Machine Learning Research (11/2024)
Algorithm 1 LS-LLM
Require:
MDP P. large language model M, model budget B, domain-specific language D, search algorithm SHC.
Ensure: An approximate solution æ to P.
1: π f ask for a policy that solves P written in from M
F evaluate π in P and return feedback
for = 1.... B 3311 do
x' -- ask for a policy that solves P written in D from M while providing F as input to M
5: F' evvaluate x' in P and return leedback
6: if x' is an improvement over π in terms of return R then
7: T+
8: F+F
return the result of SHC while using x as initial candidate
(lines 1 and 4.. The policies are requested sequentially from the model. In this way, LS-LLM can provide feedback to the LLM by rolling out the policy in the environment (o.g., by informing the model of the actions the agent has taken in the environment); the feedback is denoted as F in Algorithm [ Note that LS-LLM does not receive any feedback when requesting the first policy from M. In this case, the prompt simply requests a "strong" policy for the MDP (see Section 5.5 and the supplementary materials for details).
The best policy, in terms of the average return R, that the LLM generates is given as input to SHC, which attempts to further improve the policy with search (line D). Even the LLM is unable to directly generate strong policy, its attempt generating one might allow the search to start in a more promising part of the programmatic space. Such an initialization might allow for quick improvements with SHC.
4.1 LS-LLM in Multi-Agent Settings
In our experiments, we consider MDPs given by two-player zero-sum games. In this section, we explain Algorithm | for this setting. this setting, instead of approximating a solution to one MDP, we need to approximate a solution multiple MDPs. Each MDP is defined by fixing the opponent, and searching for a policy that maximizes the agent's return for that MDP; the opponent can be seen as part of the environment. In game theory terms, by maximizing the agent's return, approximate best response to the opponent. We use self-play algorithms to define the MDPs to be solved so that the agent can learn to play a game.
Iterated Best Response (IBR) is the simplest of such self-play algorithms. Let i and -i be the two players. IBR starts with an arbitrary policy To in [D] for one of the players, for cxample, -í, and approximates a best response Ti to mo for i. Then, it approximates a best respouse to T for -i. This process is repeated n times, which is determined by a computational budget. The last policies, Rn and 1n- are returned as an approximate solution to the game. In IBR, we use Algorithm Dto to compute each of these best responses.
The self-play process IBR follows generates a sequence of policies for i and -i, but IBR only considers the latest policy while computing a best response, which can hinder the algorithm's 's ability to learn how to play the game. Other algorithms, such as Fictitious Play (FP) [Brown] 1951). are more informative in guiding the learning process. This is because FP computes best responses to a policy that mixes all the best responses computed in previous iterations. Intuitively, FP forces the agent. to learn to play against all of its previous versions. In practical terms, when evaluating the return R of a policy in Algorithm 1 we evaluate the policy's return on multiple MDPs, one for each best response computed in the FP process. FP computed the policies T1, T2, ... T--1 far, then the average return of policy ne in Algorithm 1 EE Here, Rj is the return of in the MDP in which πÿ is fixed as part of the environment.
Other self-play algorithms, such as Double Oracle (DO) (McMahan et al. 2003), can be selective with which opponents to fix and fold into the environment. In particular, Local Learner (2L) (Moraes et al., 2023) includes only the policies that were shown to provide search guidance in the program space. As a result, the evaluation of R for both DO and 2L can be computationally cheaper than the evaluation of FP is used. This is because the evaluation be performed in fewer MDPs for DO and 21. Previous work showed that
4

---

Published in Transactions on Machine Learning Research (11/2024)
LS-LLM
Local search algorithm (here, SHC)
Self-play algorithm (here, 2L)
LLM (here, GPT 3.5)
MDP
Line 1:
Generate initial policy it (if other agents fixed by self-play algorithm, atte attempt best response; otherwise attempt strong policy)
multi-agent settings: Determine next MDP solve by fixing the other agents
2: Evaluate and return trajectory
Line 2: Generate feedback on trajectory of rt
Loop times:
Line Run local search from policy found by the LLM, trying to further improve on it. Return overall best found policy
Line 4: Generate policy based on feedback
Evaluate and return trajectory
Line 5: Generate feedback trajectory of nt'
Figure 2: Schematic view of Algorithm This scheme shows LS-LLM's interactions with the MDP (first column) and calls the L.LM (second column) and calls the local search algorithm (third column). The scheme also shows the relationship between LS-LLM and the self-play algorithm, 2T.
FP, DO, and 2L tend to perform better than IBR in the context of programmatic policies (Moraes et al. 2023 Independently of the learning algorithu used to choose the MDPs, the basic repeated operation of these algorithms is to find a programmatic policy that maximizes the agent's 's return in given MDP. In this paper, we consider LS-LLM to approximate solutions to MDPs within learning algorithms such as 2L.
5 Empirical Methodology
We evaluate in three games our hypothesis that LLMs can be used to speed up the synthesis of programmatic policies by seeding the SHC search: Poachers & Rangers (PR) and Climbing Monkey (CM) (Moraes et al. 2023), and MicroRTS (Onaañón et al. 2018). PR and CM are challenging for programmatic policies but easy for humans; MicroRTSS is a challenging real-time strategy game with an annual competition?
5.1 Poachers Rangers
PR an unconstrained sccurity game in which one of the players trics defend national park (rangers) and the other player attempts to attack the park (poachers). Given a number of gates N, rangers win the game if they defend all attacked gates; poachers win the game if they attack unprotected gate. The game is unconstrained because rangers choose to defend all N gates and poachers N gates. Programs encoding strategies for rangers are of the form def lefend (1), defend (20), while encoding strategies for poachers are of the form attack (1), attack(2), attack (10). Although the opti strategy for rangers is to trivially defend all gates, the synthesis of this stratogy through self-play was shown to be difficult (Moraes et al. 2023 This is because the program can be arbitrarily long, depending on N, and
choose to attack all
httpp::/ssites.ppt http:p/pw......tttttttttetetaete

---

Published in Transactions on Machine Learning Research (11/2024)
the algorithm needs to discover that each of the gates must be defended. The DSL used in this domain does not allow for loops, which could dramatically simplify the task. We use this domain with DSL without loops in our experiments because it represents a challenging problem for syuthesizers performing search, but it can potentially be simple for systems that leverage
systems such as LLMs.
5.2 Climbing Monkey
CM is a game in which two monkeys compete in climbing contest: the monkey that can reach the highest branch of a tree is the winner; the game ends in draw if both monkeys climb to the same branch. In this game, a monkey must climb to branch + I from i; no branch can be skipped. For example, the strategy climb (1), climb (2), climb (20) allows the monkey to reach the branch 2 of the tree; instruction climb (20) is ignored. Similarly to PR, the optimal strategy is trivial, but hard to achieve with current systems. In contrast to PR, the instructions in the optimal program must be ordered from branch to N, which presents different challenges to the algorithms. Similarly to PR, the DSL for CM also does not allow for loops.
For both PR and CM we provide as feedback F textual description of the end-game state of the match played between He and the last policy generated by the self-play algorithum, T--1- For PR, the leedback describes which gates were protected and which undefended gates the poachers attacked. For CM, the feedback reports how many branches the monkeys climbed and if they won or lost the match. The prompts with the feedback are given in Appendix C
5.3 MicroRTS
MicroRT's is a challenging real-time strategy game in which the agent controls many units in real time. The game is played a gridded map that can vary in structure and size; different maps often require different strategies. In MicroRTS, the player starts with a Base unit and, depending on the map, with other units. The Base allows the player to train Worker units and store resources; Workers can build structures (Base or Barracks), collect resources, and attack opponent units. Barracks can train combat units, including Light, Ranged, and Heavy units. These units differ in their resource cost, the amount of damage they can cause to other units, the amount of damage they can suffer before being removed from the game, and in attack range. A player wins the game if they climinate all units and structures of the other player. We use the following maps from the MicroRTS repository with the map size in brackets: NoWhereToRun (9 x 8), DoubleGame (24 x 24), and BWDistant Resources (32 x 32). The images of the maps are provided in Appendix A
The MicroRTS policies are written in Microlanguage, DSL of the game (Mariño et al. 2021 The Mi- crolanguage includes functions such as harvest and moveToUnit, which allow one to encode strong policies even in short programs. The Microlanguage uses for-loops to prioritize actions. That is, functions called earlier in a loop have a higher priority over those called later. The Microlanguage is described in Appendix C
MicroRTS is not symmetric game depending on the starting location of the players. If policy πa defeats when the former starts at location 1 and the latter at location 2, it does not mean that mi will defeat T2 if we swap their locations. To ensure a fair evaluation, each pair of policies plays two matches on each map, one in each initial location.
We used GPT 3.5, which was trained with data up to September 2021. To the best of our knowledge, no programmatic policy for PR, CM, and MicroRTS had been published online before the model's training cut-off date. The repository of Mariño et. al. (2021) contains programs written in an earlier version of Microlanguage. This earlier version of the language differs significantly from the version we use in our experiments in terms of the domain-specifie functions available and the number of parameters required in the functions. To illustrate, none of the programs available in Mariño et al. repository can be run in the interpreter of our version of the language. Moreover, Mariño et al.] did not experiment with the ToWhereToRun and ReDisstantResourrss maps that we use. Considering the differences in the language and in the maps used, it is unlikely that Mariño et al. programs have influenced our results.
https://github. Saam//arama--aae hat.arrraana-rnnnnaaaaaaaaiirrrr
6

---

Published in Transactions on Machine Learning Research (11/2024)
5.4 Baseline Systems
We evaluate LS-LLM with 2L as the learning algorithm; that is, we use 2L to determine the sequence of MDPs LS-LLM is invoked to synthesize policies for. In the results plots, we call this combination 2LS LLM). We use 2L because it was shown to outperform IBR, FP, and DO in the three games that we use in our experiments (Moraes et al.) 2023). Furthermore, 2L placed second in the 2023 MicroRTS competition, only behind a programmatic strategy written by human programmers (MicroRT'S Al Competition 2023). Therefore, (LSL)) (using local search, but without LLM) is our main basclinc. We also use FP(LS) and (BR(LS) as baselines to offer a larger pool of policies. All algorithms used the same SHC implementation. Note that in self-play algorithms, we need to compute a sequence of best-responses iie. solve sequence of MDPs. While (LSLLLLM uses an LLM to initialize each of these searches, the baselines 2L(L)), FPSLS), and IBS( use the latest best response computed to initialize the search in the programmatic space.
We did not consider deep reinforcement learning basclines because we focus on testing our hypothesis that LLMs can be used to speed up the synthesis of programmatic policies. Moreover, the 2023 MicroRTS competition showed the general trend that one should expect from such a comparison. On smaller maps, a neural policy outperforms programmatic ones. This is because the DSL used in the competition and also our experiments does not allow for fine-grained control of the game units, which neural policies can quickly learn on smaller maps. However, as the size of the maps increases, programmatie policies outperform neural ones. This is because the inductive bias the DSL provides allows for the synthesis of policies with strong high-level strategios (c.g., how to train stronger units and reach the opponent in larger spaces). See the MicroRTS Al Competition 2023 website for more information.
We also did not consider other programmatic representations such as decision trees (Bastani et al. 2018) and finite state machines (Koul ct al. 2019) in our experiments because they cither require one to first train neural model that is then distilled into a programmatic representation or directly map the neural model onto program (Orfanos & Lelis 2023 Due to this dependency using neural policy to guide the synthesis process, it is unclear how to leverage LLMs to seed up learning with these representations. One could use decision trees and finite state machines, without neural guidance, as the underlying representation of the policies. However, we would lose the inductive bias the domain-specifie language provides while still paying the cost of having to search in discrete and discontimuous spaces of programs.
5.5 Language Model and Prompts
The self-play algorithms require initial policy to start the iterative process of computing best responses. For 2L(LS-LLM), we request an initial strategy from the LLM. For all basclines, we randomly generate this initial policy, as described in Section 3 2L(LS-LLM) uses three different prompts for each domain: one for the initial policy of the first iteration of 2L (called "initial"), one for the model's first attempt to generate a best response to ne (called "firs-aateempt"). and one for the remaining B attempts (called "foodback- attempt"). We provide a description of the domain-specific language in all three prompts. The description is given as a context-free grammar with explanations of the functions used in the language. Tn first-attempt and feedback-attenpt we also provide the last policy generated in self-play, Te, and explain that this is the policy that needs to be defcated. In the feedback-attempt we provide sample of 10 actions of the model's previous attempt at a best response to ne issued in a match against тe. We do not provide all actions issued in the match due to the model's limited context length. We provide all prompts in Appendix
5.6 Experiments Performed
We performed three experiments. In the first experiment, compare (LS-LLLM on PR, CM, and the three MicroRTS maps to our basclines 2L(LS), FP(LS), and IBR(LS). These basclincs use the same local search algorithm as LS-LLM, SHC, but without LLMs. In this experiment, we compare the different approaches in terms of gates protected (PR), branches climbed (CM), and winning rate (MicroRTS). The winning rate of a policy is computed for a set of opponent policies and computed while using as opponents the policies the other evaluated systems generate. Specifically, we sum the number of victories and half the number of draws and divide this sum by the total number of matches played (Ontañón 2017 For example,
7

---

Published in Transactions on Machine Learning Research (11/2024)
Poachers & Rangers
Climbing Monkey
26
700
IBR (LS)
Number of Branches
IBR (LS)
Number of Gates
25
FP (LS)
600
FP (LS)
2L (LS)
2L (LS)
24
500
2L (LS-LLM)
2L (LS-LLM)
23
400
2
300
2
200
20
100
2-1
0
0
20
40
60
80
100
0
20
40
60
80
100
Number of Games
Number of Games
Figure 3: Average number of gates covered and branches climbed by the number of games played for 2L LLM) (ours, 2L(LS), FL()S), and IBR(LS) in the games PR and CM. The average and the 95% confidence interval are over 30 independent runs of the systems.
the winning rate of strategy that wins 5, loses 2, and draws 3 matches is 5+1.5 0.65. The performance metric of each domain is evaluated in terms of the number of games each system needs to play to achieve level of performance. The results are presented in plots where the y-axis shows the performance and the x-axis the number of games played (Figure shows two examples). This experiment evaluates our hypothesis that LS-LLM can speed up the process of learning policies, in terms of the number of games played.
The sccond and third experiments are intended to improve our understanding of LS-LLM. In the second, we evaluate LS-LLM while removing from feedback-attempl the set of actions sampled from the match played between the LLneggeerated policy and the last policy generated by the self-play algorithm. This experiment measures the impact of the foodback on the generation of an initial candidate policy for the SHC scarch.
In the third experiment, we "encrypt" the names of the functions and nonterminal symbols in the Mi- crolanguage. We still explain in the prompt what each function does, but we use meaningless names for them. For example, in the prompts used in the first and second experiments, we explain that the function DasNumberOFUnits (T, N) checks if the ally player has units of type T. In the third experiment, this function called b1, with the same explanation provided. Our goal is to verify how important the names of functions and nonterminals are to the LLM.
5.6.1 Other Specifications
All experiments were run on computers with 2.6 GHz CPUs and 12 GB of RAM. We used B = for LS- LLM. In PR, we set the number of gates to 60 and leave the number of branches for CM unbounded. We use the value = 1, 000 in Mg. SHC run with a time limit of 2, 000 seconds. Once SHC reaches a local optimum, there is still time allowed search, it restarts the search from the initial candidate the LLM has suggested. After reaching the time limit, the search returns the best program encountered in all runs. This is SHC's approximation to solution to the MDP.
6 Empirical Results
The results of our first experiment are shown in Section 6.1 ("Synthesizing Programmatic Policies") and of the second and third experiments in Section 6.2 (* (Ablaatinn Experiments").
8

---

Published in Transactions on Machine Learning Research (11/2024)
Map: NoWn (9x8)
Map: DoubleGame (24x24)
Map: BWDDsstantReoource (32x32)
1.0
1.0
1.0
IBR (LS)
IBR (LS))
ISR (U:1
RP (LS)
FP (LS)
9.51
0.5
2L (L5)
0.8
2L 11:5
0.5
25 9.5)
2L [LS- LLMI
2L (LS-LLM0
25. 8.5-LUX))
Wirening Rate
Winning Rate
0.6
Wirniing
0.-
0.2-
0.2-
0.0
10000
2050n
30000
40000
50000
0.0
10000
20000
1050n
40000
50000
0.0
10000
20000
30000
40500
50500
Number of Games
Number Garnes
Number of Garnes
Figure 4: Average winning rate by the number of games played for 2 (ours), 2L(LS), FP(LS), and IBR(LS) in MicroRTS. The wimning rate is computed by having the strategy a system synthesized, at a given number of games played, play against the strategies each of the other systems synthesized after the maximum number of games was played (50,000). The average and the 95% confidence interval are over 30 independent runs of the systems.
6.1 Synthesizing Programmatic Policies
Figure g presents the results for PR and CM. 2L(LS-LLM) represents our contribution, which uses 2L as the learning algorithm, and LS-LLM to approximate the best responses. IBR(LS), FP(L)), and 2LSS are our basclines. We refer to the algorithms in the abbreviated forms LS-LLM, IBR, FP, and 2L.
LS-LLM outperforms all baselines by a large margin. In PR, LS-LLM learns to defend all 60 gates with less than 20 games played. Often, the initial policy the LLM suggests already covers most of the gates in the game. By contrast, progress for systems that rely only on search is slow. The LLM not only generates best responses, but the best responses it generates cover more gates than is required to best respond to the poachers policy. For example, if the current. poachers policy Tp is attack then the simplest best response to it is defend which is the response an algorithm searching in the space of programs will most likely find, due to the minimal size of the program. Instead, the LLM often returns a best response such as (1)end(1), defend (2), (3), which allows quicker progress toward the policy covering all 60 gates.
We obscrve similar behavior for the CM domain, where LS-LLM quickly generates programs that climb to much higher branches than the programs the baselines generale. Most of the progress that we observe for LS- LLM comes from the best responses the LLM suggests. As programs become longer, it becomes less likely that a neighbor program will represent an improvement with respoct to the current program.
Figure shows the results for MicroRTS, where the winning rate is computed by having the policy a system generated, for a given number of games played, play against the policy each of the other systems generated after the maximum number of games used in the experiment (50,000). LS-LLM outperforms all basclines by a large margin in the three maps. Especially for the larger maps, 24x24 24 and 32 x2, LS-LLM generates stronger policies more quickly than the baselines. For example, 2T. needs to play approximately 10 times more games than LS-LLM on the 32x32 map to reach the winning rate around 60%.
Although the results on MicroRTS are similar to those in PR and CM, the explanation why LS-LLM performs better than the basclines different in MicroRTS. In PR and CM, the LLM is often able to generate a program that already solves the MDP. In MicroRTS this happens only in the early iterations of learning, when the self-play policies are weak. Later, the system generates stronger policies, the LLM fails to directly generate optimal policy. LS-LLM is more sample-efficient in MicroRTS due to its initialization of the search in the neighborhood of policies that can solve the MDP. We conjecture that the LLM helps the search explore different lypes of policy. For example, the best policies in the 9x8 map require the use of Ranged units. The LLM quickly generates programs that can train various types of unit, including Ranged units. The process of discovering such policies with search alone takes more iterations. As representative examples, we show in Appendix B two examples of policies the LLM generated, as its attempt to provide a best. response to target policy. The two policies encode different types of strategies for playing MicroRTS.
9

---

Published in Transactions on Machine Learning Research (11/2024)
Map: NoWhereToRun (9x8)
Map: NoWhereToRun (9x8)
1.0
1.0
IBR (LS)
IBR (LS)
0.8
FP (LS)
0.8
FP (LS)
Winning Rate
(LS)
Winning Rate
2L (LS)
2L (LS-LLM-Enc)
2L (LS-LLM-NO-FB)
0.6
0.6
0.4
0.4
0.2
0.2
0.0
0.0
10000 20000 30000 40000 50000 Number of Games
0
10000 20000 30000 40000 50000 Number of Games
Figure 5: Average winning rate by the number of games played for
(left) and 2L LLM-N-
FB) (right) in MicroRTS. The average and the 95% confidence interval over 30 independent runs of the systems.
6.2 Ablation Experiments
Figure 5 shows the results of the second (left) and third (right) experiments. 2L(IS-LLM-ENC) is the version of LS-LLM where we "encrypt" the name of the functions of the DSL. 21(I.S-LLM-ENC) performs similarly to IBR and is worse than FP and 2L. These results suggest that much of the general knowledge that the LLM leverages to provide initial candidates for search comes from the function names.
(L....MMM-N-- the version of LS-LLM that does not provide feedback to the LLM. 2T.(L.-LLM-- No-FB) performs comparable to the baselines, suggesting that the feedback encodes valuable information. We urejecture that the feedback allows the LLM to verify whether the program it generates achieves the goals the LLM sets to it. We make such conjecture because the LLM often explains why it generated policy, as it outputs the policy. For example, it could state that its policy will train Ranged units to protect the Base. The feedback could show that no Ranged units are being trained, allowing the LLM to modify its policy to achieve its goal in its next atlempl at generating a programmatic best response.
7 Related Work
Tnala et al. 2020 Trivedi et al. 2021 Qiu & Zhu 2022 Carvalho al.) 2024)). All of these previous works employ a form of search in programmatic spaces to solve MDPs. An SMT solver has been used to syuthesize policies for single-player puzzles (Butler et. al. 2017 and SAT solver has been used for logic games (Farzan & Kincaid 2018). We differ from all these previous works in that we use an LLM to speed up the search for programmatic policies.
Programmatic reinforcement learning is an active area of research (Verma al. 2018h 2019
Others have considered multi-agent. settings similar the ones used in our experiments, but have mainly aimed at extracting interpretable policies from neural models (Milani et al. 2022. Liu et al. 2023c). This contrasts with our approach of searching for policies in DSL-defined spaces. Still in the multi-agent setting and closer to work, various approaches have been used to find policies for two-player zero-sum games, from genetic programming (Mariño & Toledo 2022), to Monte Carlo Tree Search (Medeiros et al. 2022 and
local search (Maríño et al. 2021 Moraes et al. 2023 Previous work has focused on searching for generating policies, but has not. been enhanced by LLMs.
Previous work has used LLMs in games, but not for generating programmatic policics. Much of this work has focused on online planning in open-world games such as Minecraft or Sims-like social simulations, where LLMs have been used to perceive, plan, and act (Park et al. 2023). often decomposing long- morgzooozon goals into
10

---

Published in Transactions on Machine Learning Research (11/2024)
subtasks and monitoring their execution (Wang et al. 2023b). and/or integrating additional agent features
such as memory (Zhu et al. 2023) and/or automatic learning curricula (Wang et al. 2023a In contrast to these efforts, our work generates programmatic policies that are not modified or re re-planne in an online fashion; we use LLMs to help us generate such policies.
LLMs have also been used to help generate general policies (Celorrio et al. 2019) to solve classical planning problems (Silver et al., (023). The classical planning setting differs from ours in that it offers a formal description of the problem. This is in contrast to our setting, where only less structured description of the problem is available. Another area is the generation of code for robot decision decision-makingg making, which has seen successful use of LLMs. (ingh et al. (2023) generate plans for robotic tasks by providing Python-like code as a prompt to the LLM, including an example of a program to solve a task. The LLM then implements a function to solve another task. Liang et al. (023)) follow a similar approach, where instructions of what needs to be done can be provided as comments in the prompt code. These approaches rely on the LLM to directly solve the problem. This contrasts with our work, where we do not assume that the LLM can solve the MDP directly, so we use it to seed the search for a policy that will solve the MDP.
Another view of our work is the use of LLMs to guide local search. LLMs have been used to solve optimization problems with an interactive prompting loop that asks for new solutions based on previous solutions (Yang 2023 Guo et al.] 2023); ; they have been used to guide Monte Carlo tree search by providing a world
et al.
model and a heuristic (Zhao et al. 2023;; and LLMs have been integrated into genetic operators in many
algorithms (Lehman et al. 2022 Liu et al. 2023b Meyerson et al. 2023 Chen et al.] 2023). including multi- objective (Liu et al.) 2023a and diviitydivverstyy evolutionary algorithms (Nasir et al.) 2023). Most of the
previous work is computationally expensive because they use the LLM in every step of the search et al.
2023a), while we use it to only initialize the search.
Contemporary to our work, Liu et al. (2024) also showed how to improve the sample efficiency of a local search algorithm in the context of programmatic policies. Similarly to our results, Liu et al.] also found that LLMs can be effective in initializing the search for programmatic policies. Although the two independently developed works present similar algorithmic solutions, they approach the problem from complementary perspectives. While Liu et al.) focus on different programmatic representations (general-purpose versus domain-specific languages), we focus on the foedback we provide to the LLM, so that it can generate better initial candidate solutions. Moreover, the problem domains used in the experiments of the two papers are disjoint, further validating the idea of seeding the programmatic search with -LM-generated programs.
8 Discussion and Conclusions
The results in PR, CM, and MicroRTS showed that LLMs can be used to enhance stochastic local search algorithms in the context of programmatic policies, even if the model is used only sparingly, lo seed the search in the programmatic space. The LLM model we used in our experiments was not trained with data about PR and CM, since these games were published after the cutoff date to collect training data to train the model. Although the model had some knowledge of MicroRTS, it did not have knowledge of the Microlanguage and the programmatic policies one can write with it. However, the general knowledge encoded in the model allowed it to attempt "reasonable" programs that likely forced the search to better explore the policy space, thus improving the sample efficiency of the overall system.
Programmatic representations of policies can offer advantages over alternative representations, such as in- terpretability. The drawback of programmatic representations is that one needs to solve hard combinatorial search problems to generate programs encoding policies. Such search problems are particularly challenging because the optimization landscape is full of discontinuities and thus is not suitable for gradient descent optimization. In this paper, we presented LS-LLM, system that uses an LLM to guide the scarch for programmatic policies. The LLM is used only to initialize the search in the programmatic space, making LS-LLM a viable method given the often high monetary costs of using LLMs. We hypothesized that the use of an LLM would speed up the process of computing policies in terms of the number of samples required to learn such policies. We tested our hypothesis in three games that are challenging for current systems, including challenging real-time strategy game. Our results supported our hypothesis, the programmatic
11

---

Published in Transactions on Machine Learning Research (11/2024)
policies LS-LLM generated were stronger than those generated by current state-of-the-art systems for the same number of played games.
Acknowledgments
This research was supported by Canada's NSERC and the CIFAR AT Chairs program, and was enabled in part by support provided by the Digital Research Alliance of Canada. This research has also received funding from the project ALIGN4Energy (NWA.1389.20.22 (partly) financed by the Dutch Research Council (NWO), and from the European Union's 's Horizon Europe Research and Innovation Programme, under Grant Agreement number 101 1011204 The paper reflects only the authors' view and the EC is not responsible for any use that may be made of the information contains.
of the research programme NWA ORC 2020 which is
The authors thank the reviewers for their helpful suggestions.
References
Javier Segovia Aguas, Sergio Jiménez, and Anders Jonsson. Computing hierarchical finite state controllers with classical planning. Journal of Artificial Intelligence Research, 62:755-797, 2018. doi: 10.1613/jair.1.
11227.
David S. Aleixo and Levi H. S. Lelis. Show me the way! Bilevel search for synthesizing programmatic strategies. In Proceedings of the AAAI Conference on Artificial Intelligence. AAAI Press, 2023.
Saqib Ameen and Levi H S Lelis. Program synthesis with best-first bottom-up search. Journal of Artificial Intelligence Research, 77:1275-1311 2023.
M. Balog, A. L. Gaunt, M. Brockschmidt, S. Nowozin, and D. Tarlow. Deepeoder: Learning to write programs. In Proceedings International Conference Learning Representations. OpenReviews.net, 2017.
O. Bastani, Y. Pu, and A. Solar-Lezama. Verifiable reinforcement learning via policy extraction. In Advances Neural Information Processing Systems, pp. 2499-2509, 2018
Blai Bonet, Héctor Palacios, and Héctor Gelfner. Automatic derivation of finite-state machines for behavior control. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. (656-1653) AAAI Press, 2010.
GW Brown. Iterative solution of games by fictitious play. Activity Analysis of Production and Allocation, pp. 374-376, 1951.
Eric Butler, Emina Torlak, and Zoran Popović. Synthesizing interpretable straatttg for solving puzzle games. In Proceedings of the 12th International Conference on the Foundations of Digital Games, pp. 1 10, 2017.
Tales Henrique Carvalho, Kenneth Tjhia, and Levi H. S. Lelis. Reclaiming the source of programmatic policies: Programmaatic versus latent spaces. In The Twelfth International Conference on Leurning Rep- resentations, 2024.
Sergio Jiménez Celorrio, Javier Segovia Aguas, and Anders Jonsson. A review of generalized planning. Knowl. Fng. Rev., 34:e5, 2019. doi: 221077/5022008881880000222 URL http::://bo..org/10.00117 50269888918000221
Angelica Chen, David M. Dohan, and David R. So. Evoprompting: Language models for code-level neural architecture search. CoRR,
14838, 2023, doi: 10.48550/ ARXIV Uttpsttss://doi
org/10. org/10.48550/ 48550/arXiv 2302. 14838
Azadch Farzan and Zachary Kincaid. Strategy synthesis for linear arithmetic games. Proc. ACM Progrom. Lang,, 2.POPL))61:11611. 2018. doi: 10.1 10.1145/3158149. URL httpp:://aoi.rrg/10 /ttp://6o...rrr11001.444////444
1145/3158149
Nathanaël Fijalkow, Guillaume Lagarde, Théo Matricon, Kevin Ellis, Pierre Ohlmann, and Akarsh Potta. Scaling neural program synthesis with distribution-basee search. In AAAI, 2022.
12

---

Published in Transactions on Machine Learning Research (11/2024)
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural net- works. In Proceedings of the Thirleenth International Conference on Artificial Intelligence and Stalistics. Proceedings of Machine Learning Research, pp. 249 256. PMLR, 2010.
Pei-Fu Guo, L'ing-Hsual Chen, Yun-Da Tsai, and Shou-De Lin. Towards optimizing with large language models. CoRR, abs/ Abss/2310002201 2023. doi: 10.48550/ARXIV 2310.05200.. URL https://doi. org/10,
48550/arXiv 2310. 05204
Jeevana Priya Inala, Osbert Bastani, Zenna Tavares, and Armando Solar-Lezama. Syuthesizing program- matic policies that inductively generalize. In International Conference on Learning Representations. Open- Review.ned 2020.
Anurag Koul, Alan Fern, and Sam Greydanus. Learning finite state representations of recurrent policy networks. In International Conference Learning Representations, 2019. URL https://openreevier net/foruumiid-S1g0pee.
J. R. Koza. Genelic Programming: On the Programming of Compulers by Means of Natural Selection. MIT Press, Cambridge, MA, 1992.
Yann A. LeCun, Léon Bottou, Genevieve B. Orr, and Klaus-Robert Müller. Efficient BackProp, pp. 48.
Springer Berlin Heidelberg, 2012.
Joel Lehman, Jonathan Gordon, Shawn Jain, Kamal Ndousse, Cathy Yeh, and Kenneth O. Stanley. Evolution through large models. CoRR, abs/2206. 22086 2022. doi: 10.48550/ 1009550/AXXIV ARXIV 2206.08886. URL https:
7/doi. ort./0.gg1111 48550/arXiv 2206 08896
Jacky Liang, Wenlong Huang, Fei Xia, Peng Xu, Karol Hansman, Brian Ichter, Pete Florence, and Andy Zeng. Code as policies: Language model programs for embodied control. In IEEE International Conference on Robotics and Automation, ICRA 2023, London, UK, May 29 June 2023, pp. 9493 9500. IEEE, 2023. 10160591
doi: 10.1109 10.1109/ICRA4860 208..........110100
10///1..11 T1111111//III1E1 URL https://doi. org/10.
Fei Liu, Xi Lin, Zhenkun Wang, Shunyu Yao, Xialiang Tong, Mingxuan Yuan, and Qingfu Zhang, Large language model for multi-objective evolutionary optimization. CoRR, 2bs00 12541, 2023a. doi: 10.
ARX.V.2310.122..... .2310.12541. URL https://doi.orgge http://0....rr/1114448885/////1 (1550/ARXIV
48550/arXiv. 2310. 2310.12541
Max Liu, Chan-Hung Yu, Wei-Hsu Lee, Cheng- Wei Hung, Yen-Chun Chen, and Shao-Hua Sun. Synthesizing programmatic reinforcement learning policies with large language model guided search, 2024. URL https:
16450
Shengeai Liu, Caishun Chen, Xinghua Qu, Ke Tang, and Yew-Soon Ong. Large language models evolutionary optimizers. CoRR, abs/2310.190466, 2023b. doi: 10.48550/ARXIV223000 231.01099.10.1
URL
https://doi.org:: 48550/4855iii www.ariww.........1 2310.19048
Xiao Liu, Wubing Chen, and Mao Tan. Fidelity-induced interpretable policy extraction for reinforcement learning. CoRR, hbs/23099060997 2023c.
Julian R. H. Mariño and Claudio Toledo. Evolving interpretable strateeg for zero-sum games. Applied Soft Computing, pp. 108860, 2022. ISSN 1568-4946. doi: https://wwr http://wwwiiinnieeeeettttet///ee http://cwcc.cc.c.ooo.c.occcaaaaa
URL
Julian R. H. Mariño, Rubens O. Moraes, Tassiana C. Oliveira, Claudio Toledo, and Levi H. S. Lelis. Pro- grammatic strategies for real-time strategy games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 381-389, 2021.
H Brendan McMahan, Geoffrey Gordon, and Avrim Blum. Planning the presence of cost functions controlled by an adversary. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 536 543, 2003.
13

---

Published in Transactions on Machine Learning Research (11/2024)
Leandro C. Medciros, David S. Aleixo, and Levi H. S. Lelis. What can we learn even from the weakest? Learning sketches for programmatic strategies. In Proceedings of the AAAT Conference Artificial Intelligence, pp. 7761 7769. AAAI Press, 2022.
Elliot Meyerson, Mark J. Nelson, Herbie Bradley, Arash Moradi, Amy K. Hoover, and Joel Lehman. Language model crossover: Variation through few-shot prompting. CoRR, abs/ 12170, 2023. doi: 10.48550/ ARXIV 2302.12170. URL
htt.://a............... 12170
MicroRTS AI Competition. 2023 microrts competition results.
https://sites wow.siiieeegooggl..e...ooooooooe 2023. Accessod: Au-
micrortsai htt.a//a.....attooooooaoaaaaaaaa gust 31, 2024.
Stephanie Milani, Zhicheng Zhang, Nicholay Topin, Zheyuan Ryan Shi, Charles A. Kamhoua, Evangelos E. Papalcxakis, and Fei Fang. MAVIPER: learning dccision tree policies for interpretable multi-agent rein- forcement learning. In Machine Learning and Knowledge Discovery in Dalabuses European Conference, volume 13716 of Lecture Notes in Computer Science, pp. 251-266. Springer, 2022.
Rubens O. Moraes and Levi H. S. Lelis. Searching for programmatic policies in semantic spaces. In Proceed- ings of the International Joint Conference on Artificial Intelligence, pp. 5990-5998. International Joint Conferences on Artificial Intelligence Organization, 2024.
Rubens O. Moraes, David S. Aleixo, Lucas N. Ferreira, and Levi H. S. Lelis. Choosing well your opponents: How guide the synthesis of programmatic strategics. In Proceedings of the International Joint Conference on Artificial Intelligence, pp. 4847 4854, 2023.
Muhammad Umair Nasir, Sam Earle, Julian Togelius, Steven James, and Christopher W. Cleghorn. LI- matic: Neural architecture search via large language models and quality-diversity optimization. CoRR. abs/2306.01 102, 2023. 0100.01102
doi: 10.48550/ ARR00//RRVV.... RRXXV.23306001000 .300600112.. URL
Augustus Odena and Charles Sutton. Learning to represent programs with property signatures. In Interna- tional Conference on Learning Representations. OpenReview.nee, net, 2020.
Augustus Odena, Kensen Shi, David Bieber, Rishabh Singh, Charles Sutton, and Hanjun Dai. BUSTLE: bottom-up program syuthesis through sarning-guidees exploration. In International Conference on Learn- ing Representations, 2021.
S. Ontañón. The combinatorial multi-armed bandit problem and its application real-time strategy games. In Proceedings of the AAAI Conference Artificial Intelligence and Interactive Digital Entertainmend, pp. 58 64. AA 2013.
Santiago Ontañón. Combinatorial multi-armed bandits for real-time strategy games. Journal of Artificial Intelligence Research, 58:665 702, 2017.
Santiago Ontañón, Nicolas A. Barriga, Cleyton R. Silva, Rubens O. Moraes, and Levi H. S. Lelis. The first microrts artificial intelligence competition. AI Magazine, 39(1), 2018.
Spyros Orfanos and Levi H. S. Lelis. Synthesizing programmatic policies with actor-critic algorithms and relu networks, 2023. URL
Joon Sung Park, Joseph C. O'Brien, Carrie Jun Cai, Meredith Ringel Morris, Percy Liang, and Michael S. Bernstein. Generative agents: Interactive simulacra of human behavior. In Proceedings of the Annual ACM Symposium on User Interface Software and Technology, pp. 2:1-2:22. ACM, 2023.
Wenjic Qiu and He Zhu. Programmatic reinforcement learning without oracles. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.nd net. 2022. URL
14

---

Published in Transactions on Machine Learning Research (11/2024)
Tom Silver, Soham Dan, Kavitha Srinivas, Joshua B. Tenenbaum, Leslie Pack Kaelbling, and Michael Katz, Generalized planning in PDDL. domains with pretrained large language models. CoRR, abs/ 2bs5/2005.110 11014, 2023. doi: 10.48550/ARXII 230551.2330.11014 URL https://doi...... http:://ddoo.o/11////// wwt.///..//..../////....... 48550/arXiv. 1335.11000
Ishika Singh, Valts Blukis, Arsalan Mousavian, Ankit Goyal, Danfei Xu, Jonathan Tremblay, Dieter Fox, Jesse Thomason, and Animesh Garg. Progprompt: Generating situated robot task plans using large language models. In IEEE International Conference on Robotics and Automation, ICRA 2023, London, UK. May 29 June 2023, pp. 11523 11530. IEEE, 2023. doi: 10.1109/ICRA448991.222 101611117 URL https://dol org 10. 11t.11119////AAA 00003110161111
Dweep Trivedi, Jesse Zhang, Shao-Hua Sun, and Joseph J. Lim. Learning to synthesize programs inter- pretable and generalizable policies. In Advances in Newral Information Processing Systems, pp. 25146 25163, 2021.
A. Verma, V. Murali, R. Singh, P. Kohli, and S. Chaudhuri. Programmatically interpretable reinforcement learning. In Proceedings of the International Conference on Machine Learning, pp. 5052 5061, 2018a.
Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmect Kohli, and Swarat Chaudhuri. Program- matically interpretable reinforcement learning. In Jemnifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learn- ing Research, pp. 5045 5054. PMLR, 10 15 Jul 2018b. URL https://proceddings.u press/v80/ vermal8a. html
Abhinav Verma, Hoang Lc, Yisong Yue, and Swarat Chaudhuri. Imitation-projected programmatic rein- forcement learning. Advances in Newral Information Processing Systems, 32, 2019.
Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Voyager: An open-ended embodied agent with large language models. CoRR, abs/2305.11 2023a. doi: 10.48550/ARXIV 22200. URL https://doi /ttt::://oo.oor/10... 0tt0//00.855//aa/. 48550/arXiv. 2305.
Zihao Wang, Shaofei Cai, Anji Liu, Xiaojian Ma, and Yitao Liang. Describe, explain, plan and select: Inter- active planning with large language models enables open-world multi-task agents. CoRR, abs/2302 /bs/2232.01500 2023b. doi: 10.48550/ ARXTV .302.015600. URL https://doi. wrg/10.....oooo....ooo.o........ 48550/ 2302.01560
Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V. Le, Denny Zhou, and Xinyun Chen. Large language models as optimizers. CoRR, hts/2239.03409 2023. doi: 10.48550/ WWR.V.2209.0000... URL
https:///oi. org/10. org/10.48550/// /0r00///rxv.... 2309. 2309.03409
Zirui Zhao, Wee Sun Lee, and David Hsu. Large language models as commonsense knowledge for large- scale task planning. CoRR, abs/2305. 7/doi org/10. 48550/arXiv. 2305 14078
2023. doi: 10.48550/ARX 23055.14078. URL https:
Xizhou Zhu, Yuntao Chen, Hao Tian, Chenxin Tao, Weijie Su, Chenyu Yang, Gao Huang, Bin Li, Lewei Lu, Xiaogang Wang, Yu Qiao, Zhaoxiang Zhang, and Jifeng Dai. Ghost in the minecraft: Generally capable agents for open-world environments via large language models with text-based knowledge and memory. CoRR, abss/2305.171/ 2023. doi: 10.48550/ARXII 1714. URL sctps://doi.orge 48550/arXiv 2305 17144
A MicroRTS Maps
Figure
i shows the three MicroRTS maps used in our experiments.
15

---

Published in Transactions on Machine Learning Research (11/2024)
Figure 6: The three maps used in experiments: NoWhereToRun (9 8) the left; DoubleGame (24 x 24) in the middle; BWDistantResourres (32 x 32) on the right.
Best Response Attempt
Best Response Attempt
for Unit u)
for Unit u)
if
unberrruutsrss (Ranged, )
build (Barracks Right .1)
u. train (Heavy, U0)
u.triin (Ranged Down,
if OOponeentHas Hww.iHaaauueeerreuuuiete Light )
u.attack (Strongest)
u. train (Ranged, Up
u. train (Light Left ,5)
u. train ufueeuuutsrr oup if [OpponentHasi) u. attack (Weakest)
5p
attacck (Closest)
)
9
u. train (Light. Up, 20)
10
u. build Barracks Up, 1)
11
for ( Unit u)
12
u. attacck ( Closest)
Table 1: Examples of programmatic best responses the LLM generated to the target policy given by 2L.
B Examples of LLM-Generated Programs
We conjectured Section that LS-LLM is effective because the LLM allows it quickly explore different types of strategies. Table shows two examples of policies that the LLM generated attempts provide best response to the same target policy provided by the 2L self-play algorithm for the BWDistantResources map. The two policies encode different strategies for playing MicroRTS. The policy on the left decides the types of unit the player trains based on the units the opponent controls. For example, it will train Heavy units if the opponent controls Ranged units (lines 2 and 3). The policy on the right. focuses on training Ranged units (line 3). Later in the game, after the player controls 10 Ranged units, if resources are still available, will train Light units (line 5). These two policies do not include instructions for collecting resources and training Worker units. Therefore, while they might not be effective in practice, they offer different "template functions" that the local search algorithm further improve into effective policies.
16

---

Published in Transactions on Machine Learning Research (11/2024)
C MicroRTS Prompts
C.1 Initial Attempt (Example for 9x8 Map)
Consider 9x8 gridded map of MicroRTS, real-time strategy game. Consider this map dimensional array with the following structure:
There are total of 8 neutral resource cells situated along the central column of the map, dividing the map into two parts. Each resource cell contains 10 units of resources.
The base B1 of player 1 is located at index (1,1), which is located on the left side of the map.
The base B2 of player 2 is located at index (7,6), which is located on the right side of the map.
Each player controls one base, which initially has 5 units of resources.
The only unit player controls at the beginning of the game is the base.
Consider this Context-Free Grammar (CFG) describing programming language for writing programs encoding strategies of MicroRTS. The CFG is shown in the <CFG></CFG> tag bellow:
<CFG>
S - SS for(Unit u) if(B then S
iB) then S else $ C X
B + W.hnsNimberrUUUnt((....
w.haalassSuumbbrrrtniisss.....
u.is Type(T') u.isBuilder(()
u.canAttack()
w.opporetthassnnntthaaaaeegggg
u.canHarvest()
C u.build(T, D, NN) u.trainnT,, D,
|u.moveToUnii((, Op)
u.attack(O)) (Op) u.harvest(N)
R.attack(finRange()) |.moveeAaa(()
T Base Barracks Ranged Heavy
Light Worker
N + 0 2 3 /
7 8 8 9
10 15 20 25
50
100
> EnemyDir
Up Down Right Left
Op Strongest Weakest Closest Farthest
LessHealthy MostHcalthy Random
T,
Ally Enemy
</CFG>
17

---

Published in Transactions on Machine Learning Research (11/2024)
This language allows nested loops and conditionals. contains several Boolean functions (B) and command- oriented functions (C) that provide either information about the current state of the game commands for the ally units. The Boolean functions ('B' in the CFG) are described below:
uuhasNunberOOUUnits.,,, N): Checks the ally player has units of type T.
2. MonponeelHHs@aumeeeOOiiissSS N): Checks if the opponent player has N units of lype T.
u.lastessYummberfCCttttCC.... N): Checks if the ally player has less than N units of type T.
4. u.laveQQddUiissAtaaciin((((() Checks if the ally player has N units attacking the opponent.
u.hasUnit Vittannnssaammee/oooooneetttttt Checks the ally player has unit within distance N from opponent's unit.
Checks the ally player has units of type Worker har- 7. u.is Type(T): Checks if unit is an instance of type T.
vesting resources.
u.isBuilder(): Checks if unit is of type Worker.
9. u.canAttack(): Checks if a unit can attack.
10. TaaaUniiiTattillllnnnnAAtttta Checks if the ally player has unit that kills opponent's unit with one attack action.
11. H.opponentHasUnit ThanKKillAniitttnneetttaaaa Checks if the opponent player has unit that kills an ally's unit with one attack action.
12. u.hasUnithu ApponuunntnOpoonntteeeee opponent's 's unit.
Checks if an unit of the ally player is within attack range of an
13. Has Unttannnnnnnnllll Plaeennleeeeaaggeee Checks if an unit of the opponent player is within attack range of an ally's unit.
14. u.canHarvest(): Checks unit can harvest resources.
The Command functions ('C' in the CFG) are described below:
u.build(T, D, N): Builds N units of type a cell located the D direction of the unit.
uT, D, N): Trains units of type T on a cell located on the direction of the structure responsible for training them.
3. u.moveToUnit(T. p, O p): Commands unit to move towards the player T following criterion O_p.
u.attack(O p): Sends N Worker units to harvest resources.
h.hrrvostNN): Sonds Worker units to harvest resources.
6. I. Commands unit to stay idle and attack if an opponent unit comes within its atlack range.
u.moveAway(): Commands unit move in the opposite direction of the player's basc.
18

---

Published in Transactions on Machine Learning Research (11/2024)
'T' represents the types unit can assume. 'N' of integers. 'D' represents the directions available used in action functions.
'O p' is set of criteria to select an opponent unit based on their current state. T p' represents the set of target players.
The following 5 are some guidelines for writing the playing strategy:
1. There is NO NEED TO write classes initiate objects such as Unit, Worker, etc. There is also NO NEED TO write comments.
Use curly braces like C/C++/Java while writing any 'for' 'if 'if-else' block. Start the curly braces in the same line of the block.
Do not write 'else if block. Write 'else if((B {...}}' instead.
4. A strategy must be written inside
multiple 'for' blocks.
You must not use any symbols (for example: &&, ||, etc.) outside the CFG. In case of code like 'if (B1 && B2)', write if (B1) { if (B2) {...}}' instead.
Now your tasks are the following 7:
Understand the Boolean (B) and command (C) functions from above and try to relate them in the context of MicroRTS playing strategies.
2. Write a program in the MicroRTS language encoding very strong game-playing strategy for the 9x8 map described above. You must follow the guidelines for writing the playing strategy while writing your program.
3. You must not use any symbols (for example &&, ll. etc.) that the CFG does not accept. You have to strictly follow the CFG while writing the program.
Look carefully, the methods of non-terminal symbols and C have prefixes 'ul' in the examples since they methods of the object 'Unit u'. You should follow the patterns of the examples.
Write only the pscudocode inside "<strategr><//straeeyy"
tag.
6. Do not write unnecessary symbols of the CFG such as, 'S +', '->', etc.
Check the program and ensure it does not violate the rules of the CFG or the guidelines for writing the strategy.
C.2 First Attempt (Example for 24x24 Map)
Consider a 24x24 gridded map of MicroRTS, real-time strategy game. Consider this map as 2 dimensional array with the following structure:
There is wall in the middle of the map consisting of two columns that has small passage of 4 cells. The small passage consists of 4 resource cells each having only resource.
There are 28 resource cells at the top-left, top-right, bottom-left and bottom-right corners of the map respectively where each of them contains 10 units of resources.
The bases of player are located at indices (3,2) and (20,2), located on both sides of the wall.
The bases of player 2 are located at indices (20,21) and (3,21), also located on both sides of the wall.
19

---

Published in Transactions on Machine Learning Research (11/2024)
Each player controls bases, which initially have 5 units of resources each.
There are 2 workers beside each base. So a total of workers for each the players.
Consider this Context-Free Grammar (CFG) describing a programming language for writing programs encoding strategies of MieroRTS. The CFG is shown in the <CFG></CFG> lag bellow:
<CG>>
S SS for(Unit u) if(B) then S
if( then S else S C
B w.haNNumberOOUniss(....
whhalass/uumbrrOffttttTT..YY
w.haveQudUnisssAtakkki((((()))))
u.is uu.s__Typeee _TTppTTT
u.isBuilder()
u.canAttack()
u. halaaaUnn/Thaaiiiiiiiinneeaaaak
w.cannHarvest(()
C u.build(T, N) u.trainnT, D)
[ Op)
u.attack(Op) u.harvest(N)
w.attackffinRange()) u.moveAway()
T Base Barracks Ranged Heavy
Light Worker
+ 0 | | 7
10 15 20
25
50
100
D > EnemyDir Up Down Right Left
O Strongest Weakest, Closest Farthest
LessHealthy MostHeallhh Random
т + Ally Enemy
<CFG>
This language allows nested loops and conditionals. contains several Boolean functions (B) and command- oriented functions (C) that provide either information about the current state of the game or commands for the ally units. The Boolean functions ('B' in the CFG) described below:
O.hasSaumberOUUnittsS..... N): Checks the ally player has units of type T.
2. n.opponetthaaammmeerotttnisst N): Checks if the opponent player has N units of type T.
3. L.hsTessVomborrFFhittT.T... N): Checks if the ally player has less than N units of type T.
20

---

Published in Transactions on Machine Learning Research (11/2024)
u.haveQradUnissAttaaiiig///>>>> Checks if the ally player has units attacking the opponent
5. Ditttiitt
Checks if the ally player has unit within distance
N from a opponent's unit.
6. WhassttmbeeOWooorstttrrtttnnnnn Checks if the ally player has N units of type Worker har- vesting resources.
u.is Type(T)): Checks unit is an instance of type T.
8. u.isBuilder(): Checks if unit is of type Worker.
c.annAttcc((:: Checks if a unit can attack.
10. nns ThatKKilllnnnneAttatan Checks if the ally player has a unit that kills an opponent's unit with one attack action.
Checks if the opponent player has unit that kills 11. HLopponentHasUnie hhaareeennnnannnnnnntnaalillaaa Taattiilllnnttttnnnnttttttttt an ally's unit with one attack action.
12. Ippoonnt Rangel))) Checks if an unit of the ally player within attack range of an opponent's unit.
13. Paaaeaalaanuntttlllaaaaaaggg Checks if an unit of the opponent player is within attack range of an ally's unit.
14. u.canHHarvest(): Checks if a unit can harvest resources.
The Command functions ('C' the CFG) are described below:
1. u.build(T, D, N): Builds N units of type T on a cell located on the D) direction of the unit.
uTt D, N): Trains units of type T on a cell located on the direction of the structure responsible for training them.
3. I.moveToUnit(T O.p): Commands a unit to move towards the player T following a criterion p.
4. u.attack(O_p): Sends N Worker units to harvest resources.
h.arvest(NN): Sends Worker units harvest resources.
6. L.attackfliRRane((): Commands a unit to stay idle and attack if an opponent unit comes within its attack range.
7. u.moveAway(): Commands unit to move in the opposite direction of the player's base.
'T' represents the types a unit can assume. 'N' set of integers. DD' represents the directions available used in action functions.
'O p' of criteria to select an opponent unit based their current state. 'T p' represents the set. of target players.
Now consider the following program encoding a strategy for playing MicroRTS written inside '<strategy- 1> /strrartggy tag: <strategy-1>
21

---

Published in Transactions on Machine Learning Research (11/2024)
for (Unit u){ 2
for (Unit u)
u.build (Barracks, Right, 50)
u. train (Worker, Up. 4)
attack (Strongest) for (Unit u){
7
8
u.harvest (5)
9
10
u. w...veeoUnit (Ally, Closest)
11
for (Unit u){
u.train (Ranged, Up. 5)
13
14
</strategy-1>
Now your tasks are the following 3:
1. Analyze strategy-1 and try to analyze its weaknesses.
Write a new strategy that defeats strategy-l.
3. You need to only write this new strategy inside "<oomeeSrattry<</oomettrrttr
tag.
C.3 Feedback Attempt (Example for 32x32 Map)
Consider a 32x32 map of MicroRTS, a real-time strategy game. Consider this map as a dimensional array with the following structure:
There are two L-shaped obstacles the map, each with passage of 4 cells located at the middle of left and right sides.
There are a total of 12 neutral resource cells R located the top-right and bottom-left corners of the map. Each resource center contains 20 units of resources.
The base B1 player is located at index (6,14), which located on the left side the map.
-he base B2 of player 2 is located at index (25,17), which is located on the right side of the map.
Each player controls one Base, which initially has 20 units of resources.
There is one worker for each player bosides thoir bascs.
Consider this Context-Fres Grammar (CFG) describing a programming language for writing programs encoding strategies of MicroRTS. The CFG is shown in the <CFG></CFG> tag bellow:
22

---

Published in Transactions on Machine Learning Research (11/2024)
<CFG>
S - SS for(Unit u) S if(B) then S
if) then S else $ ||C|
B + w.haa/ammbeefttnittt(.....
wchaslesssuumberrrrnnnisss....
u.is TTpe((T
u.isBuilder()
w.canAttack()
u. wwhaaUUmiinnnpppoeeedeaaaggg
wwapppoeeetHssssuuittllllvveeee u.canHarvost()
C u.build(T, u.train(T, D, N) N.moveeooUnit(Tg... Op)
u.attack(Op) u.harvest(N)
u.attackfillRaneee)) |u.oveAway((
T Base
Barracks Ranged
Heavy
Light Worker
N 0 3 4 6 7 8
10 15 20
25
50
100
D + EnemyDir Up Down Right Left
O, + Strongest Weakest Closest: Farthest
LessHealthy MostHealthy Random
Tp > Ally Enemy
< </CFG>
This language allows nested loops and conditionals. contains several Boolean functions (B) and command- oriented functions (C) that provide either information about the current state of the game commands for the ally units.
The Boolean functions (BB' in the CFG) are described below:
O.hhsNaaberOffuntssSS,, N): Checks the ally player has units of type T.
AopponeeuHHaaNuubbeeoUUnniiiS,,. N): Checks if the opponent player has N units of type T.
u..asleesNuubbeeOUUnt[(1[11 N): Checks the ally player has less than N units of type T.
a.laveQcdUUittsstttckkkg///)))) Checks the ally player has units attacking the opponent.
DannaiiiiWitnDDtttaFFFoooopooonn Chocks the ally player has a unit within a distance from a opponent's unit.
TaaaNNunnbrOOVorreesssaavveeeeee Checks the ally player has units of type Worker har- vesting resources.
23

---

Published in Transactions on Machine Learning Research (11/2024)
u.is (Ty_):)):::: Checks if unit an instance of type T.
8. u.isBuilder(): Checks if a unit is of type Worker.
c.anAttack():: Checks if a unit can attack.
10. Taakiailllnnnnneettttaae Checks if the ally player has a unit that kills an opponent's unit with one attack action.
11. HaspponentHasUnng Wwl.aaaaaannnnnnnneeeeeeee an ally's unit with one attack action.
Checks if the opponent player has unit that kills
12. MaasUnitinOpponnnttaat Checks if unit of the ally player within attack range of an opponent's unit.
13. aarponeennnassmttmmmlllaaeeeeee of an ally's unit.
Checks if an unit of the opponent player is within attack range
14. u.canHarvost(): Checks if a unit can harvest resources.
The Command functions ('C' in the CFG) are described below:
1. u.build(T, D, N): Builds N units of type on a cell located on the D) direction of the unit.
2. u.train(T, D, N): Trains N units of type T on cell located the D direction of the structure responsible for training them.
(.TiveToUnit(T. p. 2.O.. p): Commands unit to move towards the player T p following a criterion O_p.
4. u.attack(O p): Sends N Worker units to harvest resources.
u.harvest (N): Sends N Worker units to harvest resources.
laatacklfinRang()):: Commands a unit to stay idle and attack an opponent unit comes within its attack range.
7. u.moveAway(): Commands unit to move in the opposite direction of the player's base.
'T' represents the types unit can assume. 'N' of integers. 'D' represents the directions available used in action functions.
'O p' is set of criteria to select an opponent unit based their current state. T p' represents the set of target players.
Now consider the following program encoding a stratogy for playing MicroRTS written inside '<strategy- 1>< >>< /straategy--1> lag:
<strategy-1>
for (Unit u
for (Unit u){
b.build (Barracks, Right, 50)
4
5 u. train (Worker, Up, 4)
6 attack (Strongest)
for (Unit u){ har (5)
10 moveeTouni (Ally, Closest)
11 for (Unit u){
24

---

Published in Transactions on Machine Learning Research (11/2024)
12
u. train (Ranged, Up, 5)
13
14
</strategy-1>
Here is strategy that could not defeat the above strategy:
<strategy-2>
for (Unit u){
2 for (Unit u){
3 u.build (Barracks Left, ,1)
u. traini (Heavy, Down 44
train (Worker, Up 44)
7
u. attack (Strongest)
8
for (Unit u){
9
u. h.havest (5)
10
11
u. moveTounit (Enemy, Closest)
for (Unit u){
13
u.train (Ranged, Up, 5)
14
15
</strategy-2>
The following is an encoding of the units, which we will use to give you information about match played between strategy-1 and strategy-2 above.
Base B
Worker W
Ranged Rg
Light Li
Heavy Hv
Barracks Br
The following is an encoding of the actions:
attack location att loc
return ret wait: wt
move mv
produce: prod
harvest har
The following is an encoding of the directions:
left 1
right: r
up :
down
The following is a randomly sampled sequence of actions of the match played between strategy- as player 0 and strategy-2 player 1: { (B(4) (0, (1,1), 10, 0), (u)))(u,w)) }, { (B(6) (1, (7,6), 10, 0), (r, W)) (W(16) (1, (6,5), 1, 1), (, (W(18) (1, (6,6), 1, 0) mv },
25

---

Published in Transactions on Machine Learning Research (11/2024)
(1,0), 1, mw ( (0, (2,1), 1, 1) (B)))( (1,1), 10, 0), x), },
{ (M(17) (0, (0,3), 1, 1)
{ (W(15) (1,2), 1, 0) (N))) (0, (3,0), 1, 1) mv (1)) (0, (3,1), 1, 1) (),)())) (1,1), 10, ((( (0, (0,1), 1, 0), 0), (Br (0, (2,2),
4, 0) w),
{ (W(18) (1, (7,7), 1, 0) , (122)) (5,6), 1, 1), m, (2g (1, (6,4), 1, 0) (), (,,6),)))))))))))))) 10, (1) (1, (6,5), 1, ,t) (1(20) (7,5),
1, (,, (5,5), 4, (1,xt(10)) },
{ (Rg(25) 1,
},
{ (Rg(28) 1,)
},
{ (1, (7,6), 10, (),rod((11)))) (W(33) (1, (7,5), 1, 0), my mv) (W(37) (1, (7,7), 1, 0) (B,
(6,5), 4, 0), (10) }, { (Rg(25) (0, (6,4), 1, a), 6)) (Rg (0, (6,4), 1, 0) (0, ,6) (Rg (28) (0,
(3,6), 1, 0) wt)) }, { (B(6) (1, (7,6), 2, 0) (10))
The strategy-2 failed to defeat strategy-1.
Now your tasks are the following 3:
Analyze strategy-1 and try to analyze its weaknessos. For this analysis, you may take help from the sequence of actions from the match between strategy-1 and strategy-2 provided.
Write a new strategy that defeats strategy-1.
3. You need to only write this new strategy inside coouteeSSaateys</ooootttttttttr tag.
C.4
Encrypted DSL
Consider this Context-Free Grammar (CFG) describing programming language for writing programs
encoding strategies of MicroRTS. The CFG is shown in the <CFG></CFG> tag bellow:
26

---

Published in Transactions on Machine Learning Research (11/2024)
<CFG>
S + SS for(Unit u) if(B) then S
if(() then S else $ ||
B u.bl(I, N) u.,
[u.3(T,, NN) (.bA(N)
(..5(N) u.b6(N)
u.b7(T) u.)8()
u.b9() u.b10()
w.b11() u.b12()
w..11()) u.b14()
C u.c.l N, A,C2(T,D,,) u.c((Tp.
[u.c4(Op) u.c5(N)
|u.c(() lu.c())
T +11 t2 t3 t4
[5 t6
N 0 | 3 6 7 8
10
15
20
25
50
100
D
+ dl
d2
d3
d4
d5
0 + op1
op2
op3
op4
op5
op6
op7
Tp tpl
tp2
</CFG>
This language allows nested loops and conditionals. It contains several Boolean functions (B) and command- oriented functions (C) that provide either information about the current state of the game or commands for the ally units.
The Boolean functions ('B' the CFG) are described below:
1. uT, N): Checks if the ally player has N units type T.
2. u.b2(T, N): Checks if the opponent player has N units of type T.
u.b3(T, N): Chocks if the ally player has less than N units of type T.
u.b4(N): Checks the ally player has units attacking the opponent.
5. u.b5(N): Checks if the ally player has a unit within distance N from a opponent's unit.
u.b6(N): Checks if the ally player has units of type Worker harvesting resources.
u.b7(T): Checks a unit is an instance of type T.
8. u.b8(): Checks if a unit is of type Worker.
u.b9(): Checks if a unit can attack.
10. u.b10(): Checks if the ally player has a unit that kills an opponent's unit with one attack action.
11. u.b11(): Checks if the opponent player has unit that kills an ally's unit with one attack action.
12. u.b12(): Chocks if unit of the ally player is within attack range of an opponent's unit.
27

---

Published in Transactions on Machine Learning Research (11/2024)
13. u.b13(): Checks if an unit of the opponent player is within attack range of an ally's unit.
14. u.b14(): Checks if a unit can harvest resources.
The Command functions ('C' in the CFG) are described below:
1. u.,1(T, D, N): Builds N units of type T on a cell located on the D direction of the unit.
2. u.c2(T, D, N): Trains N units of type T on cell located on the D direction of the structure
responsible for training them.
3. u.c3(T P.: Commands a unit to move towards the player T following a criterion O
4. u.c4(O p): Sends N Worker units to harvest resources.
5. u.c5(N): Sends N Worker units to harvest resources.
6. u.c6(): Commands unit to stay idle and attack if an opponent unit comes within its attack range.
7. u.c7(): Commands unit to move in the opposite direction of the player's base.
"T" represents the types of units as the following:
tl: Base
t2: Barracks
t3: Ranged
4. t4: Heavy
5. t5: Light
6. t6: Worker
DD represents directions as the following:
dl: EnemyDir
d2: Up
d3: Down
d4: Right
d5: Left
0 p' is set of criteria to select opponent unit based its current state like the following:
1. opl: Strongest
2. op2: Weakest
3. op3: Closest
4. op4: Farthest
op5: LessHealthy
6. op6: MostHealthy
'T p' represents the set of target players like the following:
tpl: Ally
tp2: Enemy
Finally, 'N' is of integers.
28

---

Published in Transactions on Machine Learning Research (11/2024)
D Poachers and Rangers Prompts
D.1 Initial Attempt
We have environment called 'Poachers and Rangers' where teams called poachers and rangers are competing with each other in national park and its surroundings. The park has 60 gates in total. The goal for each team is to defeat the opponents.
Now have the following CFG to write programs for poachers in the above environment:
- SA |A|4 A
A attack(n)
59 60
The following is the CFG to write programs for rangers:
5 - SA A
A + (ef
n + 2 3 ... 59 60
The following is the explanation of the above CFG: CFG Explanation:
S: Starting symbol that can contain one or miltiple actions.
A: Refers to the action taken by the team.
attack(n): Refers to the action to attack the n-th gate of the park
dn):nd(n): Refers to the action to defend the n-th gate of the park
n: Any positive integer up to 60.
...: It is not part of the CFG. has been used to indicate all positive numbers between.
The following some guidelines for writing the strategy program:
There NO NEED TO write classes or initiate objects such as Poachers, Rangers, Gates, etc. There is NO NEED TO write comments.
DO NOT write f...' in the program, since is not a part of the CFG.
3. Write only the action or the sequence of actions such 'attack(a)' or 'attack(a) attack(b) attack(c)) where a, b and are positive integers.
Now your tasks are the following
1. Understand all the symbols of the given CFG in the context of this given Poachers and Rangers' enviromment.
2. Write very strong strategy for poachers/rangers considering the given environment, the above CFG and the strategy writing guidelines.
You must not use any symbols (for example 'S +,, '-,,, I etc.) outside the given CFG. Write only the action or the sequence of action as mentioned in the strategy writing guideline.
29

---

Published in Transactions on Machine Learning Research (11/2024)
Replace !.? with contents meant by this symbol if there are any, then write only the strategy program inside <<strategy></strraee>>>>>> tag.
Check the strategy program and ensure it does not violate the rules of the CFG or the guidelines for writing the strategy.
D.2 First Attempt
We have an enviromment called 'Poachers and Rangers' where teams called poachers and rangers are competing with each other a national park and its surroundings. The park has 60 gates total. The goal for each team is to defeat the opponents.
Now I have the following CFG to write programs for poachers in the above environment:
5 - SA | A A + attack(n)
n + 2 3
59 60
The following is the CFG to write programs for rangers:
5 SA A
A - defend(n)
n + 1 2 3 3 59 60
The following is the explanation of the above CFG:
S: Starting symbol that can contain one or multiple actions.
A: Refers to the action taken by the team.
attack(n): Refers to the action to attack the n-th gate of the park
dnfend(n): Refers to the action to defend the n-th gate of the park
Any positive integer up to 60.
It is not part of the CFG. It has been used to indicate all positive numbers in between.
The following are some guidelines for writing the strategy program:
There is NO NEED TO write classes or initiate objects such as Poachers, Rangers, Gates, etc. There is NO NEED TO write comments.
DO NOT write
in the program, since is not part of the CFG.
Write only the action or the sequence of actions such as 'attack(a)) or 'attack(a) attack(b) attack(c)' where a, b and e are positive integers.
Now have the following strategy program for the poachers that satisfies the CFG, written inside 'cstralegy- /tttstttrtgy->>>> tag:
1> 1><
<strategy-1>
allack(1)
</strategy-1>
Now your tasks are the following
30

---

Published in Transactions on Machine Learning Research (11/2024)
Understand all the symbols of the given CFG in the context of this given 'Poachers and Rangers' environment.
Write an improved strategy for rangers that can defeat strategy-1.
3. You must not use any symbols (for example 'S - '+,, 'I', etc.) outside the given CFG. Write only the action or the sequence of action as mentioned in the strategy writing guideline.
Replace '...' with contents meant by this symbol if there are any, then write only the new strategy program inside the
tag.
Chock the strategy program and ensure it does not violate the rules of the CFG or the guidelines for writing the stralegy.
D.3 Feedback Attempt
We have enviromment called 'Poachers and Rangers' where leams called poachers and rangers are competing with each other in national park and its surroundings. The park has 60 gates in total. The goal for cach team is to defeat the opponents.
Now have the following CFG to write programs for poachers in the above environment:
5 - SA A
A + attack(n)
n 1 ... 59 60
The following is the CFG write programs for rangers:
- SA A
4 > (cfend(n)
1 2 ... 59 60
The following is the explanation of the above CFG:
S: Starting symbol that can contain one or multiple actions.
A: Refers to the action taken by the team.
attack(n): Refers to the action to attack the n-th gate the park
defend(n): Refers to the action to defend the n-th gate of the park
n: Any positive integer up to 60.
It is not part of the CFG. It has been used to indicate all positive numbers in between.
The following are some guidelines for writing the strategy program:
1. There is NO NEED TO write classes or initiate objects such as Poachers, Rangers, Gates, etc. There is NO NEED TO write comments.
2. DO NOT write "...' in the program, since it is not part of the CFG.
Write only the action or the sequence of actions such as 'attack(a)) or 'attack(a) attack(b) attack(c)) where a, b and e are positive integers.
31

---

Published in Transactions on Machine Learning Research (11/2024)
Now have the following strategy program for the poachers that satisfies the CFG, written inside <strategy- 1></strategy-I>>
tag:
<strategy-1>
attack(1)
</strategy-1>
Here a strategy writlen inside <:lralley>><//trralegyy/ lag for rangers that failed to defeat the given poachers' strategyl:
<strategy-2>
(60end(60)
</strategy-2>
The rangers following this strategy-2 defended 1 gate(s), but could not defend gate 1, whereas, the poachers following the strategy-1 aftacked gate Now your tasks are the following
1. Understand all the symbols of the given CFG in the context of this given 'Poachers and Rangers' environment.
2. Analyze why strategy-2 could not defeat strategy-1.
Write an improved strategy-2 for rangers that can defeat strategy-1.
4. You must not use any symbols (for example '', '+,,, 'l', etc.) outside the given CFG. Write only the action or the sequence of action as mentioned in the strategy writing guideline.
Replace '...' with contents meant by this symbol if there are any, then write only the new strategy program inside the
tag.
Check the strategy program and ensure it does not violate the rules of the CFG or the guidelines for writing the strategy.
E Climbing Monkey Prompts
E.1
Initial Attempt
We have an enviromment called 'Climbing Monkey' where 2 monkeys are competing with each other to climb tree. The tree has infinite number of branches. The goal for one monkey is to defeat another monkey. Now have the following CFG to write programs for the above environment:
$ - SA | A + climb(n)
n - 2 2 inffnitty
The following is the explanation of the above CFG:
S: Starting symbol that can contain one or multiple actions
A: Refers to the action taken by the monkey.
climb(n): Refers to the action to climb the n-th branch of the tree.
Any positive integer upto infinity.
...: It not part of the CFG. It has been used to indicate all positive numbers between.
32

---

Published in Transactions on Machine Learning Research (11/2024)
The following are some guidelines for writing the strategy program:
1. There is NO NEED TO write classes or initiate objects such as Monkey, Tree, etc. There is NO NEED TO write comments.
2. DO NOT write in the program, since it is not part of the CFG.
Write only the action or the sequence of actions such as 'climb(a)' or 'climb(a) climb(b) climb(c)) where a, and are positive integers.
Now your tasks are the following 5:
Understand all the symbols of the given CFG in the context of this given 'Climbing Monkey' environment.
Write a very strong strategy considering the given environment, the above CFG and the strategy writing guidelines.
3. You must not use any symbols (for example is +; '+,, I "...' etc.) outside the given CFG. Remove these symbols if there are any.
4. Replace '...' with contents meant by this symbol if there are any, then write only the strategy program inside <<straeeey></strraeee lag.
Check the strategy program and ensure it does not violate the rules of the CFG or the guidclines for writing the strategy.
E.2
First Attempt
We have environment called 'Climbing Monkey' where 2 monkeys are competing with each other to climb tree. The tree has an infinite number of branches. The goal for one monkey is to defeat another monkey.
Now have the following CFG write programs for the above environment:
- SA A A - climb(n)
2 3 .... infinity
The following is the explanation of the above CFG:
S: Starting symbol that can contain one or multiple actions
A: Refers to the action taken by the monkey.
climb(n): Refers to the action to climb the n-th branch of the trec.
n: Any positive integer upto infinity.
Tt is not part of the CFG. It has been used to indicate all positive numbers in between.
The following are some guidelines for writing the strategy program:
1. There is NO NEED TO write classes initiate objects such Monkey, Tree, etc. There is NO NEED TO write comments.
33

---

Published in Transactions on Machine Learning Research (11/2024)
DO NOT write '...' in the program, since is not part of the CFG.
3. Write only the action or the sequence of actions such as 'climb(a) or fclimb(a) climb(b) climb(c)) where a, and с are positive integers.
Now T have the following strategy program that satisfies the CFG, written inside <strategy-><//ssraaee 1> tag:
<strategy-1>
climb(1) climb(2) climb(3)
</strategy-1>
Now your tasks the following 5:
Understand all the symbols the given CFG in the context this given 'Climbing Monkey' environment.
2. Write an improved strategy that will help the monkey defeat another monkey following strategy-1.
You must not use any symbols (for example 'S - ' 'I' etc.) outside the given CFG. Write only the action or the sequence of action mentioned in the strategy writing guideline.
Replace '...? with contents meant by this symbol if there are any, then write only the new strategy program inside the <hevSSraeeg>><<eettttteyy
tag.
5.
Check the strategy program and ensure it does not violate the rules of the CFG or the guidelines for writing the strategy.
E.3
Feedback Attempt
We have environment called 'Climbing Monkey' where 2 monkeys are competing with each other to climb tree. The tree has an infinite number of branches. The goal for one monkey is to defeat another monkey.
Now have the following CFG write programs for the above environment:
- SA A A - climb(n)
2 3 ... infinity
The following is the explanation of the above CFG:
S: Starting symbol that can contain one or multiple actions
A: Refers to the action taken by the monkey.
climb(n): Refers to the action to climb the n-th branch of the trec.
n: Any positive integer upto infinity.
Tt is not part of the CFG. It has been used to indicate all positive numbers in between.
The following are some guidelines for writing the strategy program:
1. There is NO NEED TO write classes initiate objects such Monkey, Tree, etc. There is NO NEED TO write comments.
34

---

Published in Transactions on Machine Learning Research (11/2024)
DO NOT write '...' in the program, since is not part of the CFG.
3. Write only the action or the sequence of actions such as 'climb(a) or fclimb(a) climb(b) climb(c)) where a, and с are positive integers.
Now T have the following strategy program that satisfies the CFG, written inside <<srraeegy-><//strattg 1>' tag:
<strategy-1>
climb(1) climb(2) climb(3)
</strategy-1>
Here is strategy that could not improve the given strategy written inside <<srategy>>></ssateee>>>>>
tag:
<strategy-2>
climb(1) climb(2) climb(4) climb(8) climb(16) </strategy-2>
The monkey following strategy2 could climb branches, whereas, the opponent monkey following strategy could climb 3 branches.
Now your tasks are the following 6:
Understand all the symbols the given CFG in the context this given 'Climbing Monkey' environment.
2. Analyze why strategy-2 above could not improve strategy-1.
Write an improved strategy-2 that will help the monkey defeat another monkey following strategy-I.
You must not use any symbols (for example 'S +'; ''',, 'I' etc.) outside the given CFG. Write only the action or the sequence of action as mentioned in the strategy writing guideline.
5. Replace i...' with contents meant by this symbol if there are any, then write only the new strategy program inside the <rooStratog>><neewttttttt
tag.
Check the strategy program and ensure it does not violate the rules of the CFG or the guidelines for writing the strategy.
35


Reviews:
[{"review_id": "Vf8Ta0RT5N", "reviewer": "Reviewer_2wVK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The presented paper contains strong results supporting the author's goal to show that LLMs speed up search algorithms for programmatic policies. The conducted experiments clearly show that LS-LLM far outperforms traditional algorithms. The ablation experiments also show that LS-LLM performs much worse when not providing the LLM with feedback for improving its initial policy.\n\nIt is a bit unclear how much impact the traditional search algorithm has. The authors mention that in MicroRTS, the LLM often fails to generate optimal policies, which are easily found by the traditional search algorithms. They hypothesize that the LLM still helps improve results by generating different kinds of policies, thus enabling much more efficient exploration of the search space. While I can see how this makes sense, a more thorough examination of the generated types of policies would have helped support their claim.\n\nIn the ablation experiments, the authors also show that by obfuscating some of the names used in the abstract syntax tree, the results become much worse. While this is an interesting observation, it doesn't seem to add much to the claim of the paper.\n\nTo my knowledge, the approach presented in this paper is novel, and the experiments show strong results.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose utilizing large language models (LLMs) to enhance traditional search algorithms for generating programmatic policies. The general idea is to generate an initial policy in the form of an abstract syntax tree using an LLM, which is then further optimized using a search algorithm. The proposed algorithm LS-LLM goes a step further by first allowing the LLM to iteratively optimize its initial policy, using feedback from the previous runs. Once the LLM optimization has been completed, the best-performing policy is optimized using the traditional search algorithm. The authors apply this algorithm to multiple two-player zero-sum games using self-play. In this scenario, LS-LLM is repeatedly used to beat the previous best-performing policy.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- 5.4 Baseline Systems: The first sentence contains a double \"of of\" (Not critical)\n- Experiments: An analysis of generated strategies in MicroRTS would help better support your hypothesis that the LLM explores different kinds of strategies (Not critical)\n- A figure for visualizing LS-LLM with self-play would help tremendously to understand how it works. I had quite some trouble figuring out if and when the LLM is used to generate a new policy (Not critical)", "broader_impact_concerns": "No concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "MJJ8G2ymnm", "reviewer": "Reviewer_uSqq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is written clearly and easy to understand. \n\nGreat improvements for the Poachers & Rangers and Climbing Monkey environments, but on the other hand, I don't think these are very representative DSLs for program search since no control flow structures are used, only attack, defend, climb, and integer functions are available. Also, the problem domain is pretty easy to understand, so it makes sense that the LLM is so much better for these two environments. However, it's still impressive to see. \n\nIt would be interesting to see the same ablations for the other two environments as well to backup the claim of the abstract that “LLMs are effective in this setting because we give them access to the outcomes of rollouts of the policies”.\n\nWhen reading the prompts, I also have the feeling that a lot of prompt engineering was necessary to make the algorithm work. Also example strategies are provided for the LLM. Does it make a difference when you seed the 2L search algorithm with the same strategy provided to the LLM? Because currently the search algorithms without an LLM are randomly initialized. \n\nSome claims for MicroRTS in the paper are incorrect. See this part in the paper: “We used GPT 3.5 which was trained with data up to January 2022. To the best of our knowledge, no programmatic policy for PR, CM, and MicroRTS had been published online before the model’s training cut-off date.”\n\nThere are strategies available on github which were provided with the first paper when introducing the DSL as well. See for example here: https://github.com/julianmarino/LS2/blob/master/LS2_AAAI/TableInitialPortfolio/ScriptsTable.txt (June 8 2021)\n\nand here https://github.com/julianmarino/mRTS_Compiler_LS2/tree/master/Compiler_mRTS_LS2_AAAI/src/ai/synthesis/grammar (April 19 2021)\n\nThe paper states that GPT 3.5 is used with data until January 2022 but if I look on the OpenAI site it only shows GPT 3.5 turbo with data up to September 2021. Is it not possible to specify a specific version you used? Otherwise https://platform.openai.com/docs/models/gpt-3-5-turbo\n\nBoth repositories where avaiable before the cutoff date of the training data of GPT 3.5. \n\nNo source code is provided for reproducibiliy. \n\nRegarding this it is quite hard to evaluate the usefullnes of the LLM with the MicroRTS environment since the training data for GPT 3.5 is contaminated with data about it. Additionally the Microlanguage looks a lot like Java, which is the same language of all the code related to the MicroRTS environment. (which is not really a weakness of the paper but would explain the usefullness of an LLM for this DSL)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper uses LLMs to seed the local search algorithm for program search. It is a straightforward idea that shows good improvements on the used environments, especially for Poachers & Rangers and Climbing Monkey. For MicroRTS the improvements are also good but not that significant as for the two other environments, which makes sense when you look on the environment and the used domain-specific language.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Currently, it is quite difficult for me to say what should be changed to make this work acceptable, as the claim about the training data of GPT 3.5 for MicroRTS is wrong. I would appreciate a response from the authors, how they would rewrite their claims regarding this new information.", "broader_impact_concerns": "I don't see the need to add an broader impact statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Kbdz4hUc6D", "reviewer": "Reviewer_zNMB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Paper strengths and contributions\n\n**Motivation and intuition**\n- The motivation for utilizing the programming skills and general knowledge of LLMs to improve the sample efficiency of synthesizing program policies is convincing.\n\n**Clarity**\n- The overall writing is clear. The authors utilize figures well to illustrate the ideas. \n\n**Related work**\n- The authors sufficiently discuss the related work.\n\n**Experimental results**\n- The experimental results show that the proposed framework significantly outperforms local search methods.\n\n## Paper weaknesses and questions\n\n**Minor issues**\n- Typos\n    - \"LS-LLMbut\" the last paragraph of the introduction\n- SHC is not defined. I am assuming it means Stochastic Hill Climbing.\n\n**Deep RL baselines**\n- It would be interesting to see how the proposed framework and the local search methods compared to naive deep RL methods, such as PPO or SAC.\n\n**Other programmatic baselines**\n- As mentioned in the introduction, existing works have explored learning RL policies structured in decision trees or finite state machines. It would be informative if a comparison to these methods, or an explanation of why comparing these methods is non-trivial, were provided.\n\n**Other search methods**\n- This paper focuses on SHC. It would be interesting to see how other search methods perform.\n\n**Elo**\nThe winning rate is used as the evaluation metric. I wonder if it would make sense to use Elo.\n\n**Generalizability**\n- As stated in the introduction, programs can generalize to unseen scenarios better than neural network policies. Evaluating such generalizability would strengthen this work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the problem of improving the sample efficiency of methods which synthesize reinforcement learning (RL) policies described in a domain-specific language. This work presents Local Search with LLM (LS-LLM), which utilizes the programming skills and general knowledge of large language models (LLMs) to produce initial program candidates, and then further improves these programs using a local search method, e.g., hill climbing. The experiments on various grid-world tasks, e.g., Poachers & Rangers, Climbing Monkey, and MicroRTS, show that the proposed framework significantly outperforms local search methods without LLM-initialized programs. I believe this work studies a promising research direction, presents an interesting framework, and provides sufficient evaluations. In sum, I recommend accepting this paper since it presents valuable contributions that would interest the community.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please respond to my questions above.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Following from the discussions between authors and reviewers, and the final recommendations provided to me by the reviewers, I have no further requirements for revision and recommend to accept the paper as is.

Of course, preparing the camera-ready version will still allow for minor changes, and I would like to recommend / encourage the authors to remember and take into account the following:
- Some reviewers asked about sharing source code. If you are able to, please do this and include a URL for the code repository.
- Reviewer 2wVK (the reviewer with whom you did not yet actively discuss, who I think submitted their review after you last revised the paper) had some additional suggestions / requests. I would like to encourage you to still consider these (certainly fixing the typo, but you may also wish to consider the request for including some sort of figure that provides a general overview of the proposed algorithm).
Decision: Accept (poster)