Adaptive Combinatorial Allocation
This work addresses allocation problems in matching and resource distribution, offering a scalable solution with theoretical guarantees, though it appears incremental as it builds on Thompson sampling for constrained settings.
The paper tackles the problem of repeated allocation under unknown returns and constraints, such as in matching problems, by proposing a Thompson sampling-based algorithm. The main result is a prior-independent finite-sample regret bound that does not depend on the exponentially large number of allocations, and performance is illustrated using U.S. refugee resettlement data.
We consider settings where an allocation has to be chosen repeatedly, returns are unknown but can be learned, and decisions are subject to constraints. Our model covers two-sided and one-sided matching, even with complex constraints. We propose an approach based on Thompson sampling. Our main result is a prior-independent finite-sample bound on the expected regret for this algorithm. Although the number of allocations grows exponentially in the number of participants, the bound does not depend on this number. We illustrate the performance of our algorithm using data on refugee resettlement in the United States.