【CMU博士论文】数据驱动决策中的激励、信息与不确定性

机器学习（ML）模型正越来越多地在关键场景中做出或辅助决策，这些场景包括金融市场、电子商务以及物理世界。然而，从机器学习预测转向机器学习决策时会面临额外的挑战：往往需要推理世界中其他个体的激励，战略性地利用信息，并推断因果关系，而这一切通常发生在仅有部分反馈的情况下。此外，这些问题在现实决策情境中往往会相互叠加，从而要求学习者能够同时加以处理。 本论文旨在为存在信息不对称和结果不确定性的战略环境下的学习与决策奠定数学基础。通过将算法博弈论、信息经济学、在线算法、因果推断等工具和方法与传统机器学习方法相结合，本研究提出了新的框架与算法，用于理解和优化动态多智能体环境中的算法决策过程。

本论文的第一部分研究了在不同形式的额外信息可用时的激励下学习问题。主要贡献包括：第一个关于具有附加信息的 Stackelberg 博弈学习框架及其可证明保证、博弈中的元学习方法，以及利用信息设计提供算法救济（algorithmic recourse）的框架。论文的第二部分探讨了在存在结果不确定性时，带有激励约束的学习所面临的额外挑战。我们提出了两种流行因果推断方法（工具变量回归和合成控制）的策略感知（strategy-aware）版本，以及在更现实的反馈结构下的新型战略分类算法。 近年来，机器学习（ML）系统在诸多领域取得了广泛关注的成功，包括语言建模 [84]、计算机视觉 [297] 和药物发现 [206]。这些突破得益于在大规模标注数据集上的训练，使得 ML 模型能够准确预测感兴趣的量，例如文本序列中的下一个 token、图像内容或蛋白质结构。 然而，尽管准确预测是一项重要能力，在许多实际应用中，最终目标是做出优质的下游决策。因此，基于机器学习的决策被视为一个自然的前沿方向。 从 ML 预测转向 ML 决策时，会出现额外的挑战：当 ML 模型的决策会影响他人时（例如在算法招聘与贷款 [270, 64] 中），这些个体会有动机采取战略性行为。不同个体还可能拥有不同的信息来源，从而在决策时影响其行动。在这些领域中运行的算法智能体必须能够可靠地处理多源信息，同时还需推理自身与他人之间的信息不对称。更复杂的是，许多现实世界的决策任务缺乏标准监督学习所假设的清晰、结构化反馈。模型往往并非为每个决策接收到明确的标签，而只能观察到噪声大且间接的奖励信号，从而使得评价决策质量与有效学习更加困难。 上述每一类挑战都已有大量研究，但往往是孤立展开的。算法博弈论研究如何设计能够考虑自利型智能体战略行为的系统 [284]。近年来，这一方向与机器学习相交，探索学习算法在战略环境中的表现。异质与不对称信息的挑战则通过经济学中的信息设计 [63]展开，旨在理解如何披露信息以影响博弈与市场中的行为。最后，多臂赌博机（bandits）[327, 233]文献则聚焦于在不确定性下进行决策的学习算法设计。 这些领域提供了宝贵的见解，也构成了本论文的研究基础。然而，要在真实世界中利用 ML 进行决策，往往需要一种综合性方法，将这些视角加以结合。因此，本论文旨在通过融合算法博弈论、信息设计、因果推断和多臂赌博机等方法与传统 ML 技术，建立严谨的数学基础，用于应对战略性与不确定性环境下的数据驱动决策。 第二章涵盖了本论文的背景知识。第 2.1 节介绍了算法博弈论中的基本概念，包括同时博弈与 Stackelberg 博弈。这些博弈模型为研究在目标与信息不一致环境中个体的竞争与合作互动提供了结构化方式。第 2.2 节介绍了在线学习的基础，即数据按序到达而非一次性给出，正如许多重复决策场景中那样。由于数据分布可能随时间变化，在线学习智能体必须能够在（部分）反馈下动态更新策略。最后，第 2.3 节讨论了合成控制方法，它在因果推断和面板数据的反事实推理中扮演关键角色，而面板数据在许多决策情境中自然出现。 本论文的第二部分提出了在带激励的学习中，如何利用不同类型的信息来改进决策的新算法。第 3 章和第 4 章研究了 Stackelberg 博弈中的附加信息问题。在第 3 章中，我们证明了与无附加信息的情形不同，在最坏情况下无悔学习（no-regret learning）不可能实现。受此启发，我们提出了在两个自然放松条件下的学习算法。第 4 章进一步研究了在仅有赌博机反馈（bandit feedback）而非完全反馈的条件下，如何在 Stackelberg 博弈中学习。这一环境需要新的算法技巧，我们展示了如何将问题归约为领导者效用“对偶空间”中的上下文赌博机问题，并进一步将该方法应用于组合式二价拍卖中的竞价学习，以及公共与私有状态下的在线 Bayesian 说服（persuasion）问题。 第 5 章研究了博弈中的另一类额外信息：来自相似历史博弈的序列。在此，我们首次为多类经典博弈（包括双人零和博弈、一般和博弈及 Stackelberg 博弈）建立了元学习（meta-learning）保证。具体而言，我们得到的收敛速率依赖于所遇博弈序列间的自然相似性度量，同时在博弈序列完全任意时，能够回收已知的单博弈保证。 第二部分的最后两章研究了在激励下学习时的私有信息作用。第 6 章展示了如何战略性地披露信息，以向受到算法决策影响的个体提供一种“算法救济”（algorithmic recourse）。第 7 章则研究了在对被说服的战略型智能体存在不确定性的情况下的学习与说服问题。 本论文的第三部分聚焦于在激励与不确定性下学习的新算法。第 8 章研究了当智能体对算法决策做出战略性回应时，ML 模型所能观察到的反馈类型。先前工作假设智能体的标签在决策后可见，但这一假设在招聘与贷款等高风险领域往往不现实。我们提出了在弱反馈（称为“apple tasting”或单侧反馈）条件下的学习与决策算法。 第 9-11 章探讨了激励下的因果推断。第 9 章通过观察到部署的模型可被视为一种工具变量（instrument），其影响个体的可观测特征但不直接作用于结果，从而建立了战略响应与工具变量回归之间的新联系。这一视角使得在存在战略行为时仍可用工具变量回归估计因果关系。第 10 章研究了在战略行为存在时合成控制的表现。我们证明合成控制在此环境下无法准确估计因果关系，但若明确建模战略行为，则可修改以在下游决策任务中获得良好表现。第 11 章回到合成控制环境，并提出了在智能体存在战略行为且治疗服从性（treatment compliance）无法保证时的因果参数估计算法。这需要同时推理激励、不确定性与信息不对称，并借助第 6、7 章讨论的说服文献中的工具与技巧。 最后，本论文在结论部分强调了未来值得探索的方向。