How can I reduce combinatorial explosion in an MCTS-like algorithm for program induction?

Question

I'd like to develop an MCTS-like (Monte Carlo Tree Search) algorithm for program induction, i.e. learning programs from examples.

My initial plan is for nodes to represent programs and for the search to expand nodes by revising programs.

Many of these expansions revise a single program: randomly resample a subtree of the program, replace a constant with a variable, etc. It looks straightforward to use these with MCTS.

Some expansions, however, generate a program from scratch (e.g. sample a new program). Others use two or more programs to generate a single output program (e.g. crossover in Genetic Programming).

These latter types of moves seem nonstandard for vanilla MCTS.

One idea I've had is to switch from nodes representing programs to nodes representing tuples of programs. The root node would represent the empty tuple $()$, to which expansions could be applied only if they can generate a program from scratch. The first such expansion would produce some program $p$, so the root would now have child $(p)$. The second expansion would produce $p'$, so the root would now also have child $(p')$ as well as the pair $(p, p')$. Even assuming some reasonable restrictions (e.g. moves can use at most 2 programs, pairs cannot have identical elements, element order doesn't matter), the branching factor will grow combinatorially.

What techniques from the MCTS literature (or other literatures) might reduce the impact of this combinatorial explosion?

Answer 1

I think you may get some inspiration from the work on deterministic environments by Javier Segovia et al. See their paper Computing programs for generalized planning using a classical planner (2019).

If you don't have access to Elsevier's papers, I recommend that you check out the first author's profile on dblp.org. From there you will find links to open access versions of the conference paper that led up to the publication above.