A Reinforcement Learning Framework for Combinatorial Optimization

Abstract

The combination of reinforcement learning methods with neural networks has found success on a growing number of large-scale applications, including backgam-mon move selection (Tesauro 1992), elevator control (Crites & Barto 1996), and job-shop scheduling (Zhang & Dietterich 1995). In this work, we modify and generalize the scheduling paradigm used by Zhang and Di-etterich to produce a general reinforcement-learning-based framework for combinatorial optimization. The problem of combinatorial optimization is simply stated: given a finite state space X and an objective function f: X--+ 532, find an optimal state z * = argmax, eX f(x). Typically, X is huge, and finding an optimal x * is intractable. However, there are many effective heuristic algorithms that attempt to exploit