ICMLMay, 2023

加权记分贝叶斯多臂老虎机算法：通过重复曝光优化解决计算难题

PDF
TL;DR研究了一个权重计数的赌博算法，其中动作损失与最近 $m$ 个时间步骤中该动作被播放的次数的加权求和有关，并引入了 “重复暴露最优性” 的条件来最小化完备策略遗憾，提出了简单的修改后的连续消除算法，并对其进行了理论和实验分析。
weighted tallying banditrepeated exposure optimalitypolicy regretsuccessive elimination algorithmhuman memory
发现论文，激发创造
  • 阻断赌徒

    考虑到重复使用某些选项可能是不可取的或不可行的，本文提出了一种新颖的随机多臂赌博机设置，并通过映射到 PINWHEEL 调度问题证明了问题的优化累积奖励不允许有伪多项式时间算法，但它设计了一种贪婪算法和一种基于 UCB 的算法，具有一定的优异性。

    Jul, 2019

  • 计数型赌博机的完整策略遗憾界

    研究了限制对手策略的措施，旨在实现最强版本的策略后悔，即完全策略后悔。提出概念式为 “计票老虎机” 的在线学习算法，并针对该算法提供了一种具有可接受保证的算法，证明了算法的近似最优性。

    Apr, 2022

  • 短时、高容量的多臂 / 波段测试

    现代平台利用随机实验从给定的项目集（“处理”）中进行明智决策。本研究探讨了一种贝叶斯多次播放自助游问题，涵盖了具有高容量短寿命项目的多元测试（或 “多个 A/B 测试”）问题的关键特点。通过大规模领域实验证明，我们的策略比平台当前的推荐系统在总持续时间上提升了 4.32％，点击次数上提升了 7.48％。

    Dec, 2023

  • 组合半弦臂算法的一阶遗憾上界

    本文研究了在线组合优化问题中的半盲反馈，提出了一种优化算法来减少期望后悔。该算法以 L_T * 的平方根为增长率，在部分反馈方案中首次实现了此类保证，并在组合设置中首次实现了此类保证。

    Feb, 2015

  • 加权赌博机或：赌博机如何学习扭曲的非预期价值

    文章研究在多臂老虎机问题中引入代价扭曲的概率分布，提出了一些算法，并证明了这些算法在一定条件下能够达到较好的效果，同时给出了相关的理论分析和数值模拟。

    Nov, 2016

  • 用于对抗性基于效用的决斗多臂赌博机问题的相对指数加权算法

    提出了 REX3 算法来解决多臂对决问题中对于选择一对臂进行相对反馈而不是绝对反馈的问题，算法具有 O (sqrt (K ln (K) T)) 的期望有限时间遗憾上界，同时提供了从信息检索应用程序中使用真实数据的实验结果。

    Jan, 2016

  • 拥塞贝叶斯：通过短期重置实现最优路由

    该研究针对交通路线推荐问题，提出了基于拥堵信息的多臂赌博机和上下文赌博机算法，并通过仿真实验证明了算法的无后悔性。

    Jan, 2023

  • 睡眠赌徒的近最佳每个动作的遗憾界

    我们使用广义版本的 EXP3、EXP3-IX 和 FTRL 与 Tsallis 熵直接最小化每次行动的遗憾，从而获得了接近最优的 $ O (√{TAln⁡K})$ 和 $ O (√{T√{AK}})$ 的界限，并将我们的结果推广到了从睡眠专家那里寻求建议的强盗情境，从而得到了一些现有自适应和跟踪遗憾上限的新证明，并通过推广我们的结果到专家报告信心的强盗版本，得到了主要依赖于专家信心之和的置信遗憾上限。

    Mar, 2024

  • 带有复合匿名反馈的非随机赌博机

    研究非随机赌博环境下的遗憾界，提出了基于 FTRL with Tsallis entropy 的算法转化方法。

    Dec, 2021

  • 具有习惯化和恢复动态的非静态赌徒问题

    提出了 ROGUE（Reducing or Gaining Unknown Efficacy）类模型及其算法 ROGUE-UCB，可捕捉到具有非稳态现象的问题模型，经实验证明优于现有算法并应用于个性化医疗干预以增加身体活动。

    Jul, 2017