武装手臂赌徒
研究随机多臂老虎机问题的性质和限制,探讨具有在线探索特性的预测器的表现,其中简单后悔被评估,讨论简单后悔与累计后悔的关系,在有限臂数的情况下展示了一种性能下限和预测器的上限后悔,并针对连续老虎臂问题进行了研究。
Feb, 2008
本研究调查和综合了在线统计学习范例——称为多臂赌博机的领域,作为在线实验的某一类资源。我们首先探讨了传统的多臂赌博机的随机模型,然后探讨了复杂模型的分类模式,针对每种模型的复杂性与实验设计背景下的特定要求或考虑进行了说明。最后,我们提供了所有研究算法已知上限遗憾表格的决策工具,为未来理论工作提供了两方面的视角。
Oct, 2015
本文提出了一种忽略一定程度下最优性差距的Bandit算法,并以其为基础,设计优化算法Thompson Sampling(ε-TS)。研究结果表明,该算法能够在一定程度上避免过度探索问题,并在保证性能的前提下,提高计算效率。
Aug, 2020
研究了多精度多臂赌博机(MF-MAB)及其最优臂识别和后悔最小化目标,为BAI提出了成本复杂度下限,推荐两种替代忠诚度选择程序的算法框架,并确定了两种程序的成本复杂度上限,并提出了新的后悔定义,以及解决了该问题的消除算法。
Jun, 2023
设计一种不使用奖励分布信息的多臂赌博机算法,通过交替应用贪婪规则与强制探索来实现显著的后悔上界,并提供不同强制探索策略下的问题依赖性后悔上界分析方法,适用于不同奖励分布的固定和分段固定设置。
Dec, 2023
我们介绍了多臂赌博问题的一种新颖扩展,它包括一个额外的战略要素:弃权。在这个增强的框架中,智能体不仅在每个时间步骤中被要求选择一个臂,还可以选择在观察之前放弃接受随机瞬时奖励。当选择放弃时,智能体将遭受固定的后悔或获得保证的奖励。在这种增加的复杂性下,我们问是否能够开发出既渐近最优又极小最优算法。通过设计和分析算法,我们肯定地回答了这个问题,使得后悔满足相应的信息论下界。我们的结果为放弃选项的好处提供了有价值的定量洞察,为进一步探索其他具有这种选项的在线决策问题打下了基础。数值结果进一步支持了我们的理论发现。
Feb, 2024
我们引入了一种新颖的多臂赌博问题框架,其中每个臂与一个固定的未知置信集相关联,覆盖了结果空间(可以比奖励更丰富)。臂-置信集对应关系来自已知的假设类。我们定义了一种与这些置信集定义的下概率相对应的遗憾概念。等价地,这个设置可以被视为一个两人零和博弈,其中在每一轮中,代理选择一个臂,对手从与该臂相关联的选择集中选择结果分布。遗憾是相对于游戏价值定义的。对于某些自然的假设类,这些类类似于随机线性赌博问题(是结果设置的特殊情况),我们提出了一个算法并证明了遗憾的上界。我们还证明了特定特殊情况下的遗憾下界。
May, 2024