Dec, 2023

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

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

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

    Sep, 2014

  • 固定置信度下的最优臂识别

    本研究完整表征了单参数赌博机问题中最优臂识别的复杂度，并提出了一种被称作“Track-and-Stop”的策略，该策略通过的新采样规则和所提出的 Chernoff 停止规则被证明是渐近最优的，并在样本复杂度上取得了一个新的紧致下界。

    Feb, 2016

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

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

    Sep, 2016

  • 多臂老虎机中带延迟反馈的最佳臂识别

    本文研究了在多臂赌博机的延迟反馈场景下，如何利用局部反馈来提高标准算法的样本复杂度。采用模型化的方法探讨了局部反馈和延迟反馈之间的关系，并提出了一种用于处理偏差或无偏差情况下局部反馈的有效算法。另外，还针对并行多臂赌博机提出了一种新的算法扩展。在实际场景中，针对电池快速充电和野生动物走廊建设的计算可持续性领域中的策略搜索和超参数优化等问题的实验表明，利用局部反馈的结构可以显著提高标准算法的性能。

    Mar, 2018

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

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

    May, 2019

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

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

    Jun, 2020

  • 有限精度采样赌博机中的最佳臂识别

    研究了多臂赌博机问题中学习者在选择臂时精度受限的变体，并且给出了期望停留时间的渐近下限并提出了一种修改后的算法用于处理非唯一最优配置，并且针对在简单的情况下访问不重叠臂的情况给出了非渐近下限和上限。

    May, 2023

  • 关于固定预算下二臂赌博机最优臂识别的统一最优算法

    固定预算下的随机双臂赌博机最佳臂识别问题中，不存在优于均匀采样算法的算法，该问题的解决方案是引入一类称为“一致稳定算法”的自然算法，并证明该类算法与均匀采样算法的性能相同。

    Aug, 2023

  • 固定预算下的约束最佳混合臂识别的纯探索

    本文介绍了携带固定预算的约束性最佳混合臂识别问题，提出了一个基于分数函数的连续拒绝算法，结合线性规划理论，以识别最佳支持并且证明了其误识别概率在给定学习预算N和问题实例难度常数下的指数衰减。

    May, 2024

  • 多层次最优臂识别

    在本文中，我们研究多信度最佳臂识别问题，通过提出一种以梯度为基础的方法，我们找到了具有渐近最优成本复杂度的解决方案，并针对每个臂还提出了最优保真度的概念。

    Jun, 2024