BriefGPT - AI 论文速递
·
组合随机贪心赌博机
💡
原文中文，约500字，阅读约需2分钟。
📝
内容提要
本文介绍了一种新颖的组合性随机贪婪的赌博算法（SGB），用于解决多臂赌博问题。该算法通过观察每个时间步选择的一组臂的联合奖励，采用了优化的随机探索再确认的方法。实验证明，该算法在单调随机次模性奖励下，能够实现(1-1/e)的遗憾边界，并且在基数约束方面优于最先进的方法。同时，在在线受限社交影响最大化的背景下，该算法始终优于其他算法，并且随着基数的增长，性能差距也增大。
🎯
关键要点
- 提出了一种新颖的组合性随机贪婪的赌博算法（SGB），用于解决多臂赌博问题。
- SGB算法在没有额外信息的情况下，仅观察每个时间步选择的一组臂的联合奖励。
- 该算法采用优化的随机探索再确认的方法，专门设计用于具有大量基本臂的情景。
- 与现有方法不同，SGB算法仅对未选择的臂进行优化比例的抽样。
- 对于单调随机次模性奖励，SGB算法实现了(1-1/e)的遗憾边界，复杂度为O(n^(1/3) k^(2/3) T^(2/3) log(T)^(2/3))。
- 在基数约束k方面，SGB算法优于最先进的方法。
- 在在线受限社交影响最大化的背景下，SGB算法始终优于其他算法，且随着k的增长，性能差距增大。
➡️
