12:00, 27 Nov 1996, WeH 7220 Using Prediction to Improve Combinatorial Optimization Search Justin Boyan I will describe a simple statistical approach to improving the performance of stochastic search algorithms for optimization. Given a search algorithm $A$, we learn to predict the outcome of $A$ as a function of state features along a search trajectory. Predictions are made by a function approximator such as global regression or a neural net; training data is collected by Monte-Carlo simulation. Extrapolating from this data produces a new evaluation function which can bias future search trajectories toward better optima. I'll discuss my implementation of this idea, STAGE, and show promising results from two large-scale domains.