expressed in pHTN form) for the trivial reason (among others) that H will be in Chomsky normal form. For our purposes it is enough for H to generate an approximately correct distribution on plans. So the ideal evaluation is some measure of the distance between distributions (on plans), for example Kullback-Leibler (KL)
divergence:

$$D_{K L}({\mathcal{P}}_{{\mathcal{H}}^{\star}}\mid\mid{\mathcal{P}}_{{\mathcal{H}}})=\sum_{\phi}{\mathcal{P}}_{{\mathcal{H}}^{\star}}(\phi)\cdot\log\frac{{\mathcal{P}}_{{\mathcal{H}}^{\star}}(\phi)}{{\mathcal{P}}_{{\mathcal{H}}}(\phi)},\qquad\qquad\qquad(9)$$

where PH and PH∗ are the distributions of plans generated by H and H∗respectively. This measure is 0 for equal distributions, and otherwise goes to infinity.

However, as given the summation is over the infinite set of all plans, so instead we approximate by sampling, but this exacerbates a deeper problem: the measure is trivially infinite if PH gives 0 probability to any plan (that PH∗ does not). So in the following we take measurements by sampling X plans from H∗and H,
obtaining sample distributions PˆH∗ and PˆH, and then we prune any plans not in PˆH∗ ∩ PˆH, renormalize, obtaining Pˆ′H∗ (say P1) and Pˆ′H (say P2), and finally compute:

$$\hat{D}({\cal H}^{*}\mid\mid{\cal H})=D_{K L}(P_{1}\mid\mid P_{2})=\sum_{\phi}P_{1}(\phi)\cdot\log\frac{P_{1}(\phi)}{P_{2}(\phi)}.\tag{10}$$

This is not a good approach if the intersection is small, but in our experiments |PˆH∗ ∩ PˆH|/|PˆH∗ ∪ PˆH| is close to 1. This modification also imposes an upper bound on the measure, of about O(log X).

## 3.4. Experiments In Randomly Generated Domains

In these experiments, we randomly generate the oracle pHTN H∗, by randomly generating a set of recursive and non-recursive schemas on n non-primitives.

In non-recursive domains, the randomly generated schemas form a binary and-or tree with the goal as the root. The probabilities are also assigned randomly. Generating recursive domains is similar with the only difference being that 10% of the schemas generated are recursive. For measuring overrall performance we provide 10n training plans and take 100n samples for testing; for any given n we repeat the experiment 100 times and plot the mean. The results are shown in Figure 3(a).

We also discuss two additional, more specialized, evaluations.

Rate of Learning: In order to test the learning speed, we first measured KL divergence values with 15 non-primitives given different numbers of training plans.