1

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. Each edge represents a possible revision.

Many expansions involve a single program: randomly resample a subtree of the program, replace a constant with a variable, etc. It's 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, but I'm not deeply familiar with the literature or what technical terms might be most relevant.

How can I model expansions involving $N \ne 1$ nodes? Are there accepted methods for handling these situations?

joshrule
  • 51
  • 5

1 Answers1

1

Approach 1: One way would be to switch from nodes representing programs to nodes representing sets of programs. The root node would represent the empty set ${}$, 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'}$ which would itself also have the child ${p,p'}.

One downside to this approach is that, even assuming 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, because each new program can be combined with all (or most) of the previously generated programs.

Approach 2: Another way would be to switch from nodes representing programs to nodes representing meta-programs describing an initial program and a series of revisions to that program. For example, MCTS might search for expressions in something like this grammar:

Program  -> Empty
          | Program > OneProgramRevision
          | Program Program >> TwoProgramRevision
OneProgramRevision -> AddDatumAsException
                    | SampleStatement
                    | RegenerateSubtree
                    | Delete
                    | ...
TwoProgramRevision -> Concatenate
                    | Crossover
                    | ...

This is just a cartoon: one would need to add details parameterizing each of the various revisions.

joshrule
  • 51
  • 5