2020/11/04 by Maximilian Kasy, Kasy, Maximilian, Alexander Teytelboym +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Econometrics (econ.EM) #FOS: Computer and information sciences #FOS: Economics and business #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2011.02330
openalex publication_date 2020/11/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.