Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routing

Understand

Value-function-based methods have long played an important role in reinforcement learning.

• However, finding the best next action given a value function of arbitrary complexity is nontrivial when the action space is too large for enumeration.
• We develop a framework for value-function-based deep reinforcement learning with a combinatorial action space, in which the action selection problem is explicitly formulated as a mixed-integer optimization problem.
• As a motivating example, we present an application of this framework to the capacitated vehicle routing problem (CVRP), a combinatorial optimization problem in which a set of locations must be covered by a single vehicle with limited capacity.