  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.
