自适应组合分配

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

摘要翻译：
我们考虑的设置是，分配必须反复选择，回报是未知的，但可以学习，决策受到约束。我们的模型涵盖了双边和单边匹配，即使有复杂的约束。我们提出了一种基于汤普森抽样的方法。我们的主要结果是该算法的期望遗憾上的一个先验独立的有限样本界。虽然分配的数量在参与人数中呈指数增长，但限制并不取决于这个数字。我们用美国难民重新安置的数据来说明我们算法的性能。
---
英文标题：
《Adaptive Combinatorial Allocation》
---
作者：
Maximilian Kasy and Alexander Teytelboym
---
最新提交年份：
2020
---
分类信息：

一级分类：Economics        经济学
二级分类：Econometrics        计量经济学
分类描述：Econometric Theory, Micro-Econometrics, Macro-Econometrics, Empirical Content of Economic Relations discovered via New Methods, Methodological Aspects of the Application of Statistical Inference to Economic Data.
计量经济学理论，微观计量经济学，宏观计量经济学，通过新方法发现的经济关系的实证内容，统计推论应用于经济数据的方法论方面。
--
一级分类：Statistics        统计学
二级分类：Machine Learning        机器学习
分类描述：Covers machine learning papers (supervised, unsupervised, semi-supervised learning, graphical models, reinforcement learning, bandits, high dimensional inference, etc.) with a statistical or theoretical grounding
覆盖机器学习论文（监督，无监督，半监督学习，图形模型，强化学习，强盗，高维推理等）与统计或理论基础
--

---
英文摘要：
  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.
---
PDF下载：
--> English_Paper.pdf (223.57 KB)

2022-4-16 11:29:49 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：econometrics Participants Econometric Constraints Statistical

自适应组合分配Maximilian Kasy*Alexander Teytelboym 2020年11月5日我们考虑的设置是，分配必须反复选择，回报未知但可以学习，决策受到约束。即使有复杂的约束条件，我们的模型也可以实现单边匹配和单边匹配。我们提出了一种基于汤普森抽样的方法。我们的主要结果是一个先验独立的样本边界，这是该算法的预期遗憾。虽然分配的数量随着参与者的数量呈指数增长，但界限并不取决于这个数字。我们使用美国难民重新安置的数据来说明我们算法的性能。1导言适应性实验使用在实验过程中获得的信息来优化对后来研究参与者的待遇分配。例如，如果求职者随着时间的推移到达一份工作，决策者可以使用早期工作的结果来改善对后来参与者的劳动力市场干预（Caria et al.,2020）。例如，利用这些信息，适应性实验可以被用来最大化研究参与者的福利，或者为随后的政策选择提供信息（Kasy和Sautmann,2020）。然而，在许多政策环境中，政策制定者并不简单地在几种干预措施之间进行选择。这些资源是典型的scar ce，可行的资源分配可以用组合约束来描述。例如，如果政策制定者想在教室组成A影响学生结果的情况下将学生分配到教室（Graham et al.，2010)，她必须确保所有学生都被分配到教室，教室的ca pacity不超过d，并且分配n尊重学生在p Opulation中的人口组成。如果政策制定者希望在家庭影响孩子的结果时将孩子分配给其他家庭，她需要确保兄弟姐妹被安置在一起，寄养家庭与学校和家庭分开（麦克唐纳，2019；罗宾逊-科尔特，2019)。如果政策制定者想给租户分配社会住房，她需要确保住房符合*牛津大学经济系，maximilian.kasy@Economics.ox.ac.uk。|牛津大学经济系，Alexander.teytelboym@Economics.ox.ac.uk。我们感谢丹尼尔·普里·维特拉和马诺斯·佩尔迪卡基斯的出色研究。租户的需求和尊重等待名单的优先事项（塔克拉尔，2016年；瓦尔丁格，2018年；范·迪克，2019)。如果医生想要为病人分配治疗组合以克服困难，她需要确保这些治疗在适当的时间实际上是可用的，并且可以组合。组合资源的限制可能会使适应性实验相对于无约束的情况更加困难，正如多臂强盗文献中所考虑的那样，因为可能的分配数量可能是巨大的。例如，将学生分配到教室的方式的数量随着学生人数的增加而增加。这可能会导致计算性的错误（需要在一个大的离散空间上进行优化）和统计性的错误（必须了解许多分配的expe c ted奖励）。然而，值得注意的是，尽管存在这些缺陷，我们还是实现了接近无约束casecan的性能。本文考虑了一种扩展Thompson抽样（Thompson,1933）思想的自适应分配策略。在存在组合资源约束的情况下，该策略接近于最优策略，以最大化expe参与者的结果。我们所支持的一般设置是fo llowing。

决策者可以获得一定数量的选项（例如，匹配），但只能选择满足资源约束（例如，一对一匹配）的分配（选项组合；例如，匹配）。决策者选择一个分配，并观察每个选择的选项的结果。每一个选择的结果都是一个回报。决策者的目标是随着时间的推移，从她选择的所有选择中最大化预期的累积回报；等效地，决策者a ims使e xpe cted遗憾最小化，即在每个周期中最优选择组合之间的期望di-everence。这种类型的o f设置在文献中被称为具有线性r e wards的组合半强盗设置（Audiber t et al.，2011)。“组合”是使决策者选择方案的组合；“半强盗”是因为决策者可以对每一个匹配的结果进行分析，而不仅仅是对整个匹配的结果进行分析；和“线性奖励”，因为目标函数是一个ll匹配的r ewards的和。我们的主要理论结果是在我们的设置中使用Thompson抽样得到的最坏情况后悔的一个界。Thompson抽样是标准盗匪问题的经典启发式；它要求每个动作被选择的概率等于该动作是o ptima l的poster ior概率。我们的理论结果是有三个原因的。首先，最坏情况下的预期遗憾并不依赖于批处理大小，即使可能的操作的数量（即分配）在批处理大小中以expension的方式增长。其次，我们的边界是在样品中，不依赖于简单的方法。第三，我们的界是先验独立的，允许任意统计依赖于匹配结果；这对于匹配背景尤其相关。我们将我们的方法应用于将重新安置的难民与美国当地的豁免权相匹配的问题（Bansak等人，2018年；Trapp等人，2020年）。我们的数据涵盖了所有这些与现有界限的对比，现有界限要求在各种选择中事先独立，如下文所述。2014年和2020年美国重新安置机构HIAS的难民。我们的目标是在难民抵达后三个月内增加他们的就业机会。向当地社区分配难民的机会受到限制。地方社区对一年可以安置的难民总数有配额，来自同一个家庭的难民必须被安置在一起。隐含优化问题相当于一个“多背包问题”（Trapp et al.，2020；Delacr\'etaz et al.，2019)，我们的论文与关于多臂强盗问题的文献有很大联系。除了试图刻画解析解（如Gittins(1979))，我们还分析了Thompson(1933)，Agrawal and Goyal(2012)和Kaufmann et al.（2012）已经证明，对于给定的参数情况，在banditsettings中的Thompson算法的期望遗憾的渐近界与由Lai and Robbins，1985)导出的任何bandit algor ithm的遗憾的下界相匹配。Wang和Chen(2018)为组合半强盗环境下的Thompson算法提供了一个分布依赖的遗憾；我们的r e sult是无分布的。使用Thompson算法的自适应实验已经被提出用于诸如药物试验(Berry，2006)、推荐系统（Kawale et al.，2015)和客户获取（Schwartz et al.，2017)等应用。最近，适应性实验已经被部署在开发上下文中的Figureld实验中（Kasy and Sautmann,2020；Caria et al.，2020)。

第二节描述了我们的组合半强盗设置和Thompson启发式；第2.1节接着讨论了这一总体框架所涵盖的几个例子。第三部分给出了我们的主要理论结果和直觉证明。第4节讨论了在实践中实现的几个考虑因素，包括模型和先验的回声，从后验采样的方法，以及统计推断。第5节讨论了基于激励应用的校准模拟。附录a简要回顾了信息论，这是证明我们的主要结果所必需的。所有证明都可以在附录B.2中找到。我们用小写字母表示所有随机变量（例如，a)和用小写字母表示随机变量的实现（例如，a)。决策者可以获得选项（例如，匹配或项目）的可行选项和行动j∈1，..，J，但只有su-cient资源来选择其中的M≤J。我们证明了teby A{A∈{0,1}j:kak=M}是一组可行的选项组合。如果决策者面临额外的分配约束，A是严格子集。决策者的行动a∈a是选择的可行组合。时间、潜在结果和可观测性该计划发生在一定的周期数t=1,。...,T.在每个周期中，存在一个向量yt∈[0,1]jof potentialOutsures,其中Yjtis是在周期t中r选项j的潜在结果。向量Ytare I.I.D.跨周期。我们用θj表示选择j的平均潜在结果（或平均结构函数），即θj=e[yjtθ]。决策者对向量θ∈[0,1]j持有一个先验信念，其中我们允许这个先验对选项j的任意依赖。在每个周期中，决策者选择一个作用于∈{0,1}j。如果决策者选择行动a，他们观察选择的选项j的结果（选项j对于whichaj=1)，即向量(a)=(aj·yjt:j=1,...,j）。（1）我们假设“稳定的单位治疗值”（即，没有s pillips或干扰），在意义上，YJTs不依赖于任何J的选择作用AJ\'ts。请注意，这个假设与这样的设置是一致的，即Yjtis本身是由一个选项j组成的多个个体之间相互作用的平衡结果，就像下面讨论的应用中exa mple的c ase一样。给定我们关于可观察性的假设，在周期t开始时可用的信息由ft={(at\',yt\'(at\')):1≤t\'<t}给出。（2）在本文中，关于ETT的子脚本t表明，期望是在后验分布Pt(·)=P(·Ft)下评估的，其中FTS是在周期t开始时可用的信息。决策者可以根据信息Ft以及可能的基于随机的n装置来选择他们在一个周期t开始时的行动，该装置在统计上独立于跨周期并且独立于潜在结果序列(Yt)tt=1。目标和政策如果决策者在周期t中选择行动a，他们将得到等于ha，yti。因此，在采取行动a时，决策者的期望给定了θ，这在周期t中是相同的，equalsR(a)=et[ha,ytiθ]=ha,θi。（3）决策者希望最大限度地增加累积的期望报酬，e“txt=1R(At)#。（4）本文中的期望取自于行动选择的随机性，即po结果的抽样分布Yt和先验分布θ。表示bya=一个可行的行动，使s的期望报酬最大化条件为θ（但不是向量Yt上的条件），即a=a rgmaxa=ar(a)=argmaxa=aha,θi。（5）决策者的目标等价于te”txt=1(R(a*)-R(At))#的期望遗憾最小化。（6）求解该动态随机协同优化问题计算量很大。

与其解决它，我们建议决策者采用以下启发式策略。在每一个时期，决策者应根据a是o ptimal的后验概率，即对于每一个a∈a,Pt(at=a)=Pt(aut=a),从行动集a中采取行动a。（7）这一假设特别意味着ET[At]=ET[a*]。这种启发式方法称为Thompson抽样，最初是由Thompson(1933)为适应性实验中的治疗分配而引入的。2.1例子在下面我们讨论了我们的一般框架所涵盖的几个例子，以及下面定理1中提供的遗憾界。这些例子对应着与topractical相关的政策问题。它们还说明了文献中研究过的各种组合分配问题是如何融入我们的框架的，如赋值拓扑、一对一匹配、多对一匹配、背包问题等。对于每一个这些问题，几个选项可能与相同的基础参数相关，因此对于某些j，j′，在先验概率为1的情况下，θj=θj′。例如，在一对一匹配的情况下，每个ma tched对对应于一个选项，但对于所有匹配对j与在匹配的两侧观察到的协方差tes是相同的。示例1（将难民分配到当地社区）。难民安置机构每周都要做出决定，将抵达的难民家庭分配到当地社区。a行动a是难民fa milies与当地社区的匹配。选项的数量J是两个家庭-地区对之间不同匹配的数量，批量大小M等于给定一周内到达的难民家庭的数量。我们将在第5节be LOW中更详细地考虑这个示例。示例2（养父母分配）。寄养家庭通常能够同时接待几个寄养儿童（马·麦克唐纳，2019；罗宾逊-科尔特，2019)。ac tion a是家庭和孩子之间的多对一匹配。可行的行动要求没有一个家庭接收超过其所能容纳的孩子，所有兄弟姐妹都被匹配到同一个寄养家庭，儿童被寄养在学校附近。在观测上相同的optio ns j中，即在具有相同观测协变量的儿童和家庭的匹配中，参数θja是一个更完美的depe。实施例3（Peer e-ects和clas sroom compositio n）。假设政策制定者愿意选择cla ssrooms的性别组成，以便最大限度地提高学生的表现（Graham et al.，2010)。假设学生有两种类型，男孩和女孩。教室里有一定数量的学生。一个动作a将学生分配（即分组）到c教室。对于学生的产出来说，教室的身份并不重要，但同伴的身份却很重要。选项J的数量等于所有学生集合中教室大小的子集的数量。批大小M等于教室的数量。如果除了性别之外，学生之间的观察没有差异，那么在女生和女生数量相同的教室里，prio r表现出完全依赖关系。3性能保证接下来我们陈述了我们的主要理论结果。这一结果为我们建立的Thompson抽样的经验遗憾提供了严格的最坏保证。定理1。在第2节的假设下，e“txt=1(R(a*)-R(At))#≤rjt M·log jm+1.定理1的讨论定理1中的遗憾界的几个特征是相位化的。首先，这个界是一个有限的样本界。没有最大的样本极限，也没有余项。其次，这个界不依赖于θ的先验分布。此外，它允许先验分布在θ的分量上具有任意的统计相关性，正如我们的激励例子所要求的那样。

第三，这个界限意味着汤普森抽样在我们的环境中达到了由Audibert e t Al证明的收敛速度。(2014)，在我们的环境中，极大极小遗憾以√jt M的速度增长，直到对数阶。定理1限定了最坏的情况，期望regr和ac ross所有p个可归类的先验，求和的acrossunits。为了得到每单位最坏情况下的期望遗憾，将该表达式除以T M,whichyels boundqJ·lowjm+1(2T M）。这个界在样本大小的r ate为1的情况下，即以1/√t m的速率为0。该定理进一步表明，这个最坏情况下的预期遗憾是随着可能选项J的数目而增长的，例如，除掉对数项）J（忽略对数项）。值得注意的是，最坏的情况下，regr et不会以批量大小M增长。尽管事实上第2节的设置允许JM.S.规模的行动集。为了比较，应用Russo和Van Roy(2016)中命题3提供的Thompson抽样的具有独立武器的Inbuntits的最坏情况遗憾界和ields amuch的更大的界，它与JM log JM成比例增长。相反，遗憾界定理1的增长就像一个简单的带J臂的多臂强盗一样。定理1证明的直觉定理1的证明在附录B中被忽略。这个证明建立在信息论的几个定义和标准r e sults之上，这些定义和标准r e sults将在附录A中回顾。在这里，我们只概述了我们证明中的一些关键步骤。首先，我们使用Pinsker不等式来将预期遗憾与observatio ns提供的关于最优行动A*的信息联系起来，其中信息是用海报iors和先验的Kldatem来度量的。Pinsker不等式对于Bernoulli r andom变量esb和B′，(e[B]-e[B′])≤dkl(B，B′)。引理1将Pinsker不等式应用于预期遗憾认知中出现的形式为ET[θja*j=1]-et[θj]的词。这种对Pinsker不等式的使用是Russo和Van Roy(2016)证明的核心。其次，遵循Bubeck和Sellke(2020)中引入的一些思想，引理2将KL-距离与事件A*j=1的熵相关联。这两个引理结合起来，就可以用A*j后验的熵约简来约束期权j的预期遗憾。第三，也是最后，引理3表明，在整个期权j中，以及在整个时间周期t，c中，总的熵约简不超过每个事件A*j=1的先验熵之和，它以M·plog jm+1为界。定理1的证明结合了这三个引理。与文献的关系，我们的证明建立在Russo和Van Roy(2016)首创的信息关联理论方法（特别是引理1和2以及其中的命题6）和Bubeck和Sellke(2020)提出的该方法的一些变体（特别是引理13）的基础上。尽管与他们的论点有密切的关系，但定理1从这些论文中提供的界限出发，进行了如下的限制。Rus so和Van Roy(2016)中最失败的例子是他们的提议6。然而，他们的结果要求在t的任何时候，θ的分量的先验分布和后验分布在统计上是独立的。相反，上面的理论em1允许任意依赖。这对于匹配环境尤其相关，在匹配环境中，先前分布中的独立性很难证明是合理的。Bubeck和Sellke(2020)中最接近的结果是他们的Theore m 21。他们的结果是渐近的，而不是提供一个精确的样本界。

Bubeck和Sellke(2020)的主要兴趣是对遗憾界的渐近重新定义，它在最佳可实现的遗憾中缩放，允许后者收敛到0；4.Thompson抽样用于匹配问题4.1模型和先验用于匹配解决的实现为了在实践中获得良好的性能，我们提出的过程依赖于为数据生成过程指定一个合适的模型，以及为底层参数指定一个合适的先验分布。我们gene rally提倡使用默认先验信息，这些先验信息在类型之间是双向的和对称的，同时结合了关于依赖结构的合理结论。表1提出了一些用于匹配设置的模型和先验信息的变体，涵盖了我们主要的激励示例，包括在我们的实证应用中使用的示例。对于这些变体中的每一个，我们假定选项j由类型s ujandtypes vj之间的双边匹配组成。对于每一个可能的匹配（选项），潜在的结果yjta是从均值为θj的某个分布中得出的。我们需要指定Yjt的这种分布，以及参数θjsrovs j的联合优先分布。这些模型中的每一个都假定选项-e-ectθji是由typee-ectsàuujandàvvj的和决定的，加上相互作用e-ectàuvuj，vj。对于连续的结果，我们可以确定θji是由这个和直接给出的。对于二元或离散的结果，我们假定θjis由应用于此和的logit链接函数给出。对于离散有界s uppo rt的结果模型，Yjtis的分布由平均para米θjas和一个色散参数m控制。后者是相对于更严格的二项式模型允许更大的偏差，这可能会给单个观测的信息量带来过多的重量。4.2推论为了实现Thompson抽样，我们需要从后验样本中对θ进行抽样。对于标准参数值的统计推断，这个后验也是r提升。这种推论通常是次要目标，除了使参与者的结果最大化的主要目标之外。Suchinference可能是贝叶斯的，使用与assig NmentAlgorithm中相同的p osterior分布。另外，这种推论也可以基于排列检验，如下面所述。马尔可夫链蒙特卡罗和贝叶斯对分级先验的推论，如第4.1节所讨论的，一般情况下，后验不是封闭形式的，但我们可以使用马尔可夫链蒙特卡罗(MCMC)方法从后验r中对θ进行抽样。这样的MCMC方法只需要我们指定后验密度直到一个乘法常数（通常，直到后验密度的分母，这是由观测数据的边缘密度给出的）。MCMC方法的基础是构造一个MarkovTable 1：模型和先验s,用于匹配连续Outcomesyjtén(θj,σ)θj=γuuj+γvvj+γuvuj,vjàuujén(0,τγu),γvvjén(0,τγu),γvvjén(0,τγv),γuvjén(0,τγuv),γuvjén(0,τγuv),二元OutcomesyjtéBernoulli(θj)θj=1+exp-γuuj+γuvj+γuvuj,vjéjéuujén(0,τγu),n（μ,τγuv),离散结果有界支持{0,。..,y}yjtébeta-二项式(αj,βj,y)aj=m·θj,bj=m·(1-θj)θj=1+exp-^auuj+àvvj+àuvuj，vj...................................................................................................................................对于连续的结果，超参数分别由σ，τγu，τγv，τγuvand和μ给出；对于二元的结果，超参数分别由τγu，τγv，τγuvand和μ给出；对于有界支持的离散的结果，超参数分别由τγu，τγv，τγuvand和μ给出；对于有界支持的离散的结果，超参数分别由τγu，τγv，τγuvand和μ给出。对于这些超参数，我们提出了一种使用先验的方法：收敛于一个由相关参数给出的遍历分布的链。构造这类马氏链的方法多种多样；其中之一是哈密顿蒙特卡罗。

在我们的应用中，我们使用在软件STAN（Carpenter et al.，2017)中实现的哈密顿蒙特卡罗从后验样本中采样。设θtbe是MCMC在很长的预热期后从给定的后验样本fts中提取。chooseat=argmaxa∈Aha,θti。（8）然后遵循Thompson抽样所需的分布，即满足方程（7）。为了得到给定历史Ft的参数θj的rm1-α可信集，从pose中抽取θt，并根据θj的α/2和1-α/2分位数形成可信区间。随机化推论贝叶斯推论的另一种选择是随机化（置换）推论。在治疗E和ECT估计的上下文中，可以用r和M推理来检验治疗不存在任何outco me的零假设，因此，对于所有单位i和治疗值0,1,例如yi=yi。在我们的设置上下文中，我们需要修改这个零假设。置换推论证明了在零假设H下，对于任何反事实行为，我们指定了反事实结果向量Yt(a)，在许多感兴趣的情况下，可能有不止一种合理的方法来指定这样一个无效假设和相应的反事实结果向量。为了说明这一点，考虑一对一匹配的情况（例如，难民与当地社区的匹配），其中每个选项j对应于难民家庭与当地社区的匹配。我们可以用两个例子来形式化“ma tching无关紧要”的无效假设。我们可以反对这样一个假设，即难民的结果是相同的，无论他们被分配到哪个社区。我们可以考虑这样一个假设，即无论哪个难民被分配到那里，结果都是相同的。给定一些事实结果的特定条件，我们可以通过迭代地重新运行汤普森采样算法来采样反事实历史。在每个周期s中，从给定的后验值～ft\'处画出～θt\'和相应的～at\'。基于要测试的无效假设，推算一个反事实的外部推算器yt\'(～at\')。通过添加～at\'，yt\'(～at\')来更新历史ft\'，并为下一个期间迭代。一旦t\'=t，c计算teststatistic的实现作为～ft的函数。重复此过程以生成最大统计量的抽样distr，以及相应的临界值和p值，以测试在考虑下的空假设。5适用范围5.1难民重新安置美国历来是世界上最大的重新安置难民目的地，2016年接纳了78,340名难民。有大量证据表明，难民和当地社区之间的最初匹配极大地影响了难民的社会经济结果（Bansak e t al.,2018；Trapp e t al.,2020）。然而，当地社区的能力受到美国ZF的严格监管。因此，美国的一个重新安置机构(HIAS)利用其名为安妮·摩尔的推荐系统优化了这些难民的安置。然而，安妮对难民就业的估计是静态的，来自每年的套索回归运行（Trapp et al.，2020)。在这里，我们利用安妮·摩尔使用的数据，以便在现实的限制下对我们提议的程序进行校准模拟，希望在未来为安妮·摩尔的实际难民安置提供信息。数据我们的数据涵盖了2005年10月至2020年9月期间由HIAS重新安置的所有难民。总共有37,149名难民，构成15,523个案件（即家庭）。我们关注每个家庭主要申请人的就业情况。对于家庭中的每个主要申请人，我们观察三个二元变量：申请人是否处于主要工作年龄(25-54)，他们的性别，以及他们是否说英语。我们还观察了家庭的规模，以及家庭被重新安置的地方。

我们进一步观察初选申请人是否与美国有任何联系。与美国有联系的申请人（例如美国居民的朋友或家人）会自动被重新安置到其美国联系所居住的社区。没有美国证书的申请人可以被安排到HIAS运营的任何社区。最后，我们不确定主要申请人是否在抵达后90天内被雇用。这是州ZF用来评估美国移民安置机构绩效的一个关键指标。我们的数据中有57个。在整个考虑期间，我们放弃了任何一个重新安置的案例少于150个的A级，留给我们17个A级。所有的A级都是匿名的。根据可观察到的情况，我们将难民分为8个“类型”u，同时将17个a类中的每一个划分为单独的“类型”V类。这意味着我们可能希望了解8·17=136个参数（获得就业的概率）。如上所述，a类收容难民的能力有限，能力是重新安置的总人数（主要申请人及其家庭成员）。一个人的能力有时会改变一年中的最佳水平。对于我们的模拟，我们保守地将每年可用的capa城市设置为特定年份实际重新安置到每个城市的没有美国联系的难民总数的110%。Trapp等人在他们的分析中说。（2020）由于观察数量少，也汇集了一些人才。安置机构被允许超过其人才能力的10%，无需进一步批准；然而，在实践中，由于随机性难民的减少，机构有时不得不寻求批准或能力的扩大和减少。动态容量管理超出了本文的范围，因此每个设备的配额是其年容量的110%除以12。模拟设计我们模拟的匹配过程如下。在现有数据中，对于每个月，我们考虑了该月由HIAS重新安置的所有难民。Wematch与美国有联系的难民与他们的实际联系。对于所有没有美国联系的难民，我们使用上面讨论的Thompson算法将他们匹配到一个hold liates。这种匹配必须满足上面描述的a个liates的容量限制，以及refumefamilies的不同规模。从后验结果求解给定的Drawθ下的最优匹配问题是所谓的多重背包问题。任何剩余的容量和任何不匹配的关系都将被转移到下一个月。然后，我们使用汤普森算法对分配的难民进行反事实的推论。基于校准的参数值θ。这些校准的参数值被重置为二进制结果的贝叶斯分层模型的后验均值，在4.1节中描述了d。结果正在进行中。参考S.Agrawal，S.和Goyal，N.(2012)。多武装土匪问题的thompson抽样分析。《学习理论会议》，第39-1页。Audibert，J.-Y.，Bubeck，S.和Lugosi，G.(2011)。组合预测对策的极大极小策略。第24届学习理论年会论文集，107-132页。Audibert,J.-Y.,Bubeck,S.和Lugosi,G.（2014）。在线组合优化中的遗憾。运筹学数学，39(1):31-45.班萨克，费维达，海穆勒，狄龙，汉加特纳，劳伦斯，韦恩斯坦（2018）。通过数据驱动的算法分配改进难民的融合。科学，359(6373):325-329。贝里，博士（2006）。贝叶斯临床试验。《自然评论药物发现》，5(1):27-36.Bubeck,S.和Sellke,M.（2020）。thompson抽样的一阶贝叶斯遗憾分析。《算法学习理论》第196-2页33。Caria,S.Gordon,G.Kasy,M.Osman,S.Quinn,S.和Teytelboym,A.（2020）。策略选择实验中的Adaptivetreatment分配。Mimeo.Carpenter,B.Gelman,A.Ho Chine Man,M.

D、Lee、D、Goodrich、B、Betancourt、M、Brubaker、M、Guo、J.、Li、P和Riddell、A.(2017)。Stan：一种概率程序设计语言。统计软件学报，76（1）。Delacr Etaz,D.,Kominers,S.D.,Teytelboym,A.等。（2019年）。建立难民安置机制。技术报告，J.C.Gittins(1979)。强盗过程和动态分配指标。皇家统计学会学报：B系列（方法学），41(2):148-164.格雷厄姆，B.S.，Imbens，G.W.和Ridder，G.(2010)。在存在社会溢出的情况下测量种族隔离的e----一种非对等度量方法。技术报告，国家经济研究局。Kasy,M.和Sautmann,A.（2020）。策略选择实验中的适应性治疗分配。经济计量学，即将出版。考夫曼，E，Korda,N.和Munos,R.（2012）。Thompson抽样：一种渐近最优的时间分析。在算法学习理论国际会议上，199-213页。斯普林格。Kawale,J.,B ui,H.H.,Kveton,B.,Tran-Thanh,L.和Chawla,S.（2015）。在线矩阵分解的汤姆森采样。载神经信息处理系统的进展，第1297-1305页。Lai,T.L.和Robbins,H.(1985)。渐近e？CIE？nt自适应分配规则。应用数学进展，6(1):4-22.麦克唐纳，博士（2019）.寄养：一个动态匹配的appr oach。技术报告，Mimeo.Mackay，D.J.(2003)。信息论，推理和学习算法。坎布里奇大学出版社，Robinson-Cort\'es，A.(2019)。谁被安置在哪里，为什么？寄养安置的实证框架。Russo,D.和Van Roy,B.（2016）。汤普森抽样的信息论分析。机器学习研究学报，17(1):2442-2471.施瓦茨，布拉德洛，费德，P.S.（2017）.使用多臂ba ndit实验，通过DisplayAddisment实现客户交流需求。市场营销学，36(4):500-522.塔克拉尔，n.(2016).公共住房分配问题：理论和来自匹兹堡的证据。技术报告，哈佛大学。汤普森，W.R.(1933)。从两个样本的证据看一个未知概率超过另一个未知概率的可能性。Biometrika,25（3/4）：285-294.Trapp,A.C.,Teytelboym,A.,Martinello,A.,Andersso n,T.,Ahani,n.等。（2020年）。难民安置中的Plac与优化。运筹学。范·迪克，W.(2019)。住房的经济后果。技术报告，芝加哥大学Kenneth C.Gri-N经济系。Waldinger,D.（2018）。通过市场设计以实物转让为目标：公共住房分配的显性偏好分析。技术报告，纽约大学，Wang,S和Chen,W.（2018）。组合半强盗的Thompson抽样。简评信息论本节我们回顾了关于熵、互信息和KL-散度的一些基本概念和事实。关于进一步的背景，见MacKay(2003)（特别是第8章），以及Russo和Van Roy(2016)中的第3节。在我们的研究中，只要把注意力限制在伯努利的情况下就足够了，这样我们就可以以元素的形式引入下面的解释。设A是期望为p的Bernoulli随机变量，设A′是e×PE为Q的Bernoulli随机变量。我们通过允许参数A和pto可互换地使用d来重载符号。o熵:H(A)=H(p)=-[p log(p)+(1-p)log(1-p)]。(A1)oKL散度:DKL(A,A\')=DKL(p,q)=p log pq+(1-p)log 1-p1-q。(A2)oPinsker不等式:(E[A]-E[A\'])=p-q≤dkl(p，q)=dkl(A，A\')。(A3)o作为后验散度的互信息：对于任意随机变量或向量F，设p(F)=e[AF=F]。ThenI(a；F)=E[DKL(p(F)，p)]。(A4)o条件熵:H(AF)=E[H(p(F))]。(A5)o互信息的熵约化形式:I(A；F)=H(A)-H(AF)。