Nov, 2023

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

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

    本文研究了随机线性武装的固定置信度下的最佳武器识别问题，目标是在最小化采样预算的同时确定最佳武器。设计了一种简单的算法，其采样复杂度与已知的特定实例下界匹配，在几乎必然的情况下一致性和期望上。此算法依赖于跟踪最佳比例的武器采样规则，而且可以很少更新而不影响其理论保证。此外，与现有的最佳武器识别策略不同，我们的算法使用的停止规则不依赖于武器数量。实验结果表明，我们的算法明显优于现有算法。本文还对具有连续武器集的线性武装的最佳武器识别问题进行了首次分析。

    Jun, 2020

  • 线性赌博机中的最优臂识别

    本文研究线性贝叶斯最优化模型中的最优臂选择问题，提出样本分配策略来识别具有固定置信度的最优臂，并在最小化样本预算的同时改进了全局线性结构估计附近最优臂的奖励值，并将其与最优实验设计中使用的 G - 最优准则进行比较。

    Sep, 2014

  • 广义线性赌博机中最佳臂的识别

    针对广义线性赌博机的最佳臂识别问题，提出了第一个算法，并在模拟中评估其性能和采样效率。该算法旨在最小化确定足够接近最佳臂所需的臂拉取次数。

    May, 2019

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

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

    Jul, 2023

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

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

    Dec, 2023

  • 通过赌博反馈进行良好的手臂识别

    提出了一种新的随机多臂老虎机问题称为好臂识别，在解决好臂识别过程中面临独特的置信度的探索 - 利用困境并为此提出了一种算法以最小化每个过程的样本数量，该算法在样本复杂度上达到了理论下限并已通过实验得到验证。

    Oct, 2017

  • 未知方差的双臂高斯赌博机中局部最优固定预算最佳臂识别

    我们提出了一种在自适应实验中估计方差的策略，并展示了在变量未知情况下该策略在渐近情况下是最优的。

    Dec, 2023

  • 快速和遗憾最优的最佳臂识别：基本限制和低复杂度算法

    通过介绍一种新算法 ROBAI 和其变种，该研究识别并解决了在带有双重目标的多臂赌博机问题中达到最优臂的同时最大化奖励的难题；并对算法的停止时间、样本复杂性以及与经典 UCB 算法相比的性能进行了理论分析和数值实验，揭示出了经典 UCB 算法中的 “过度探索” 现象。

    Sep, 2023

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

    我们提出了三批最佳臂识别（Tri-BBAI）算法和几乎最优的批量最佳臂识别（Opt-BBAI）算法，分别在渐近和非渐近设置中实现了最优的样本复杂度和批量复杂度，并设计了一种独立的程序来检查是否消除了最佳臂。

    Oct, 2023

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

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

    Feb, 2024