RLDM Conference 2019 Conference Abstract
Reinforcement Learning for Dynamic Set Packing
- Michael J Curry
- Duncan C McElfresh
- Xuchen You
- Cameron Moy
- Tom Goldstein
Set packing is a classic combinatorial optimization problem: given a pool of elements, and a list of feasible subsets of those elements, choose subsets that contain as many elements as possible, with the constraint that the subsets must be disjoint. Many useful problems can be formulated in this way: we focus on the problem of finding the best clearing for a matching market of the type used for kidney exchange. Even very abstract versions of this problem are NP-hard, but much more complicated and realistic models based on this problem are frequently solved in practice by reduction to integer linear programming (ILP). Dynamic set packing is a generalization of set packing where there are multiple opportunities to match, and where elements may arrive or depart over time. This is a good model of the decision making process for an institution running a matching market: participants may arrive and depart, and the institution can wait to match some of them if it might be more efficient. Yet in practice, institutions tend to only consider the static problem, greedily performing a maximal matching at fixed time intervals. We wish to use reinforcement learning to find state-dependent matching policies that outperform this greedy approach. Our policies will not directly output a solution to the set packing problem, but will instead decide whether or not to have an ILP solver find a maximum weighted match, or else bias it to include or avoid certain elements in its solution. We hope the work will be of direct practical use for real-world matching markets, and of more general interest to anyone who wishes to approximately solve combinatorial optimization problems in dynamic settings. Inspired by recent work in computer science, which finds that some RL agents learn policies similar to known worst-case-optimal algorithms, we also hope to see how the learned policies may be similar or different to results from the economics literature about market thickness.