Optimizing Discrete Spaces via Expensive Evaluations: A Learning to Search Framework


  • Aryan Deshwal Washington State University
  • Syrine Belakaria Washington State University
  • Janardhan Rao Doppa Washington State University
  • Alan Fern Oregon State University




We consider the problem of optimizing expensive black-box functions over discrete spaces (e.g., sets, sequences, graphs). The key challenge is to select a sequence of combinatorial structures to evaluate, in order to identify high-performing structures as quickly as possible. Our main contribution is to introduce and evaluate a new learning-to-search framework for this problem called L2S-DISCO. The key insight is to employ search procedures guided by control knowledge at each step to select the next structure and to improve the control knowledge as new function evaluations are observed. We provide a concrete instantiation of L2S-DISCO for local search procedure and empirically evaluate it on diverse real-world benchmarks. Results show the efficacy of L2S-DISCO over state-of-the-art algorithms in solving complex optimization problems.




How to Cite

Deshwal, A., Belakaria, S., Doppa, J. R., & Fern, A. (2020). Optimizing Discrete Spaces via Expensive Evaluations: A Learning to Search Framework. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04), 3773-3780. https://doi.org/10.1609/aaai.v34i04.5788



AAAI Technical Track: Machine Learning