The Effect of the Selection Method on Learning

We tested MICRO-HILLARY with the minimum-to-minimum and any-to-better selection strategies. The learning resources consumed are shown in Table 5. The statistics of the acquired macro sets are shown in Table 6. The performance of the problem solver using these macros is shown in Table 7.

Table 5: The learning resources consumed while learning in the 15-puzzle domain using various selection methods. Each number represents the mean over 100 learning sessions.

	Operator applications		CPU seconds		Problems
Selection method	Mean	Std.	Mean	Std.	Mean	Std.
Minimum-to-better	498,172	74,047	735	218	60	4.2
Minimum-to-minimum	22,211,450	27,096,382	5,461	5,298	426	434.0
Any-to-better	572,622	117,330	618	362	65	9.3

Table 6: The statistics of the macro sets acquired with various selection methods. Each number represents the mean over 100 databases.

	Total number		Mean Length		Max Length
Selection method	Mean	Std.	Mean	Std.	Mean	Std.
Minimum-to-better	14.16	0.74	8.38	0.20	18.0	0.0
Minimum-to-minimum	104.04	98.92	109.90	90.38	348.4	172.8
Any-to-better	42.06	4.43	8.20	0.15	18.0	0.3

Table 7: The utility of the learned macros with various selection methods. The results are first averaged over the 100 problems in the test set and then averaged again over the 100 macro sets.

	Operator		Expanded		CPU		Solution
	applications		nodes		seconds		length
Selection	Mean	Std.	Mean	Std.	Mean	Std.	Mean	Std.
Minimum-to-better	688	21	47.4	1.3	0.30	0.01	149.5	0.19
Minimum-to-minimum	1281	332	43.5	2.1	0.84	0.12	251.5	50.08
Any-to-better	1396	132	46.4	0.7	0.39	0.03	143.8	3.20

These results confirm our analysis in the previous section. The minimum-to-minimum strategy acquires macros that are unnecessarily long, causing a large increase in the learning resources required. Also, because the macros are longer, they are less general and many of them are acquired before quiescence. The any-to-better strategy acquires unnecessary macros, which leads to a larger branching factor and lower utility.