- J. Boyan, A. Moore, S. Fahlman, Tom M. Mitchell, Thomas G. Dietterich. 1996. Learning Evaluation. Abstract: Evaluation functions are an essential component of practical search algorithms for optimization, planning and control. Examples of such algorithms include hillclimb-ing, simulated annealing, best-rst search, A*, and alpha-beta. In all of these, the evaluation functions are typically built manually by domain experts, and may require considerable tweaking to work well. I will investigate the thesis that statistical machine learning can be used to automatically generate high-quality evaluation functions for practical combinatorial problems. The data for such learning is gathered by running trajectories through the search space. The learned evaluation function may be applied either to guide further exploration of the same space, or to improve performance in new problem spaces which share similar features. Two general families of learning algorithms apply here: reinforcement learning and meta-optimization. The reinforcement learning approach, dating back to Samuel's checkers player 1959] but with more recent successes on backgammon Tesauro, 1992] and job-shop scheduling Zhang and Dietterich, 1995], is based on asynchronous dynamic programming with value function approximation. The currently-popular algorithms , Q-learning and TD() with neural networks, run slowly and may even be unstable. I will evaluate several original value-function-approximation algorithms tailored for combinatorial optimization domains. The meta-optimization approach, which has also been applied to game-playing Pol-lack et al., 1996] and combinatorial optimization Ochotta, 1994], is conceptually simpler: we assume a xed parametric form for the evaluation function and optimize it directly. These methods, lacking the theoretical advantages of dynamic programming, have been ignored by the reinforcement-learning community; however, recent advances 1 in local optimization Moore and Schneider, 1996] may help make them superior to reinforcement learning in practice. My research will develop both methods and evaluate them empirically. I will apply these techniques to all or most of the following large-scale combinatorial domains: VLSI channel routing; treatment planning for radiation therapy; scheduling a factory production line; connguring the subsystems of the NASA Outer Planet Or-biter; and move selection in the game of backgammon. I will also validate my new algorithms on standard problems from the optimization and control literatures. Finally , a byproduct of this research will be a software package for public use.
