Oct, 2023

批处理最佳臂识别的最优算法

PDF
TL;DR我们提出了三批最佳臂识别（Tri-BBAI）算法和几乎最优的批量最佳臂识别（Opt-BBAI）算法，分别在渐近和非渐近设置中实现了最优的样本复杂度和批量复杂度，并设计了一种独立的程序来检查是否消除了最佳臂。
batched best arm identificationsample complexitybatch complexitytri-bbai algorithmopt-bbai algorithm
发现论文，激发创造
  • 最优二元法用于最佳手臂识别和流体分析

    针对最佳臂识别问题，本文提出了一种基于阈值的最优排名算法，通过对强度的函数分配进行采样来识别最佳臂，分析表明该算法在极限情况下是最优的。

    Mar, 2024

  • 差分隐私最佳臂识别

    最佳臂识别（BAI）问题在数据敏感应用中得到广泛应用，研究此问题时考虑了固定置信度下的本地和中心模型的差分隐私（DP）要求，并提出了相应的算法，以实现隐私与效用之间的权衡。

    Jun, 2024

  • 差分隐私最佳臂识别的复杂性及固定置信度

    通过定量隐私成本，确定 BAIR (Best Arm Identification under Differential Privacy) 问题的样本复杂度下界，提出了 AdaP-TT 算法作为 BAIR 的隐私 - 效用折中方案，并通过实验验证了理论结果。

    Sep, 2023

  • 线性赌臂机中的鲁棒最佳臂识别

    我们研究了基于线性奖励的鲁棒最佳臂识别问题（RBAI）。选择近乎最佳的鲁棒臂是我们的主要目标，该过程涉及每轮选择臂并通过探索潜在对手行动来评估其鲁棒性，尤其适用于使用模拟器并寻找实际转移问题中的鲁棒解。我们提出了基于实例的线性奖励的鲁棒最佳臂识别问题的下界，并提出了静态和自适应赌博算法，其样本复杂度与下界相匹配。在合成实验中，我们的算法有效地识别出最佳的鲁棒臂，并与 “预言家” 策略表现相似。作为应用，我们研究了糖尿病护理以及学习对标准计算器不准确的胰岛素剂量建议的过程。我们的算法在识别不同年龄段患者的鲁棒剂量值方面证明了其有效性。

    Nov, 2023

  • 具有固定预算的局部最优最佳臂鉴别

    通过实验设计和策略分析，本研究旨在在固定的实验轮数下，识别具有最高预期结果的最佳治疗方案，以及减少误判的概率和通过计算概率下界来设计最优策略。

    Oct, 2023

  • 具备鲁棒性的线性赌臂机算法的 A/B 测试与最佳臂识别

    我们研究了在线线性赌臂问题中的固定预算最佳臂识别问题，并提出了一种能够在非稳态环境下稳健识别的算法。

    Jul, 2023

  • 批处理多臂赌博机问题中的最佳臂识别

    最近在许多实际场景中出现了多臂赌博问题，其中由于代理人等待反馈的时间有限，必须对臂进行批量抽样。这些应用包括生物实验和在线营销。当臂的数量很大而批次的数量很小时，问题进一步复杂化。我们考虑了批量多臂赌博问题中的纯探索。我们引入了一个通用的线性规划框架，可以将不同理论设置中的目标纳入其中，以便在最佳臂识别中使用。线性规划导致了一个两阶段算法，可以实现良好的理论性能。通过数值研究，我们证明了该算法与某些 UCB 型或 Thompson 抽样方法相比也具有良好的性能。

    Dec, 2023

  • 贝叶斯框架下的固定置信度最佳臂识别

    在贝叶斯设置下，我们研究了固定置信度最佳臂识别问题。我们证明了传统的 FC-BAI 算法在贝叶斯设置下会导致任意次优的性能，并且介绍了一种连续淘汰的变体，其性能与下界匹配，仅有一个对数因子的差距。模拟实验验证了理论结果。

    Feb, 2024

  • 关于最佳臂识别的最优样本复杂度

    研究最优臂辨识问题，发现新算法和上下限优化，并提出一个新的关于最优样本复杂度的猜想。

    Nov, 2015

  • 固定预算差分私有最佳臂辨识

    在差分隐私约束下，研究固定预算探索期的线性赌臂问题，通过最大绝对确定性原则构建满足差分隐私约束的策略，得到其错误概率的上限和下限，并展示其与赌臂问题复杂性、亚最优的臂差异和差分隐私参数相关的指数级衰减特性。此外，该研究还提供了独立感兴趣且对其他赌臂问题的错误概率下限证明具有重要作用的一些辅助结果，填补了先前文献中固定预算探索期下差分隐私约束情况下最优臂识别的研究空白。

    Jan, 2024