论文标题
自适应组合分配
Adaptive Combinatorial Allocation
论文作者
论文摘要
我们考虑必须重复选择分配，回报尚不清楚但可以学习的设置，并且决策受到限制。我们的模型涵盖了双面匹配，即使具有复杂的约束也是如此。我们提出了一种基于汤普森抽样的方法。我们的主要结果是与该算法的预期遗憾有关的先前独立的有限样本绑定。尽管分配的数量在参与者的数量中呈指数增长，但界限并不取决于此数字。我们使用有关美国难民重新安置的数据来说明算法的性能。
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.
