Feb, 2024

基于先验的分配策略在结构化赌博机中进行贝叶斯固定预算最佳臂识别

PDF
TL;DR我们研究了基于贝叶斯的固定预算最佳臂识别（BAI）在结构化赌博问题中的应用，提出了一种算法，该算法基于先前的信息和环境的结构使用固定分配，我们对该算法在各种模型上的性能给出了理论上的界限，包括首次基于先验信息的线性和分层 BAI 的上界。我们的主要贡献是引入了新的证明方法，相比现有方法，该方法对多臂 BAI 的界限更紧。我们广泛比较了我们的方法与其他固定预算 BAI 方法，在各种场景下展示了其一致且稳健的性能，我们的工作提升了我们对结构化赌博中基于贝叶斯的固定预算 BAI 的理解，并突显了我们方法在实际场景中的有效性。
bayesian fixed-budget best-arm identificationstructured banditsfixed allocationsprior-dependent upper boundsmulti-armed bai
发现论文，激发创造
  • 未知方差的双臂高斯赌博机中局部最优固定预算最佳臂识别

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

    Dec, 2023

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

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

    Jan, 2024

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

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

    Feb, 2024

  • 在贝叶斯多臂老虎机优化中利用相关性和预算限制

    本文介绍了一种基于贝叶斯方法的多臂赌博机最佳臂识别优化方法，其着重于建模与多臂之间的相关性，相比已有的方法在允许的函数评估数目较小时能够取得更优的效果，在自动机器学习工具箱等实际应用中表现良好。对多种方法进行对比分析，阐明了它们不同特征之间的相对优劣。

    Mar, 2013

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

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

    Jul, 2023

  • 具有异质奖励方差的固定预算的最佳臂识别

    研究在异质奖励方差的固定预算设置下的最佳臂识别问题，提出两种方差自适应的算法：SHVar 和 SHAdaVar，分别用于已知奖励方差和未知奖励方差情况下，通过不均匀预算分配实现对高方差臂的偏好，本文还给出了误判最佳臂的概率界限。

    Jun, 2023

  • 多臂赌博机中最优臂选取的顺序消除算法

    研究了多臂赌博机中的最佳臂辨识问题，提出了一个基于顺序淘汰算法的通用框架，并基于采样机制和每轮淘汰臂数量提出了性能评估指标，设计了一种按剩余臂数的非线性函数划分预算的算法，能够在纯探索场景下获得改进的理论保证和实验性能。

    Sep, 2016

  • 多臂赌博机模型中最佳臂识别的复杂度

    本文介绍了多臂老虎机模型的性能表现，并提供了特定情况下的下限和匹配算法。此外，还提供了改进的序贯停止规则以及两个独立的技术结果。

    Jul, 2014

  • 基于固定置信度的级联赌博机的最佳臂识别

    该研究设计并分析了 CascadeBAI 算法，该算法适用于级联赌博框架中找到最佳集合的 K 个项目，提出了一种新的随机变量类型作为左侧子高斯随机变量，使用一个紧密的 Bernstein 类型浓度不等式，推导出 CascadeBAI 的时间复杂度的上界，并且通过推导出时间复杂度下界显示 CascadeBAI 在某些实用范围内的性能是最优的，并通过广泛的数值模拟证实了 CascadeBAI 的有效性以及时间复杂度上限的紧密性。

    Jan, 2020

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

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

    Jun, 2020