本文研究了一种多臂赌博机问题变体,其中每个机械臂的期望奖励是未知参数的函数,并且将机械臂分成不同的组,我们提出了一种有效的算法 UCB-g 来解决该问题,并证明该算法最优性,并针对非静态环境提出了扩展算法 SW-UCB-g。
Feb, 2018
本文提出了一种基于乘数 bootstrap 的非参数和数据相关的 UCB 算法,并进一步将二阶校正融入该算法,在理论上,我们推导出了在比标准次高斯性更弱的尾部假设下的多臂老虎机的问题相关和问题无关的后悔边界,数值结果表明 UCB 算法相比其他基线在一系列多臂和线性老虎机问题中都有显著的降低后悔
Jun, 2019
本文考虑了分布保持不变,但在未知时间发生改变的非稳态赌徒问题,研究了两种算法:折扣上限置信区间和滑动窗口上限置信区间,并通过 Hoeffding 不等式得到了后者的上界,对不优的赌博机被玩的次数期望进行了上界估计并证明了存在性突然性改变时的遗憾下界,证明了折扣上限置信区间和滑动窗口上限置信区间的匹配下界一致性。
May, 2008
提出抵御恶意攻击的新型样本中位数算法和探索辅助上限置信区间算法,并通过多个仿真和实验表明它们能够在多臂赌博机问题中实现 sublinear regret。
Feb, 2020
本文研究了随机预算多臂赌博问题,并提出了一种名为 ω-UCB 的新的上置信界(UCB)采样策略,该策略使用了不对称置信区间,并表明该方法具有对数遗憾且在合成和真实设置中始终优于现有策略。
Jun, 2023
本文提出了一种分布无关、数据驱动的上置信界(UCB)算法,结合最近发展的重新抽样中位数法(RMM)方法,对称奖励分布的研究中生成近乎最优的后悔边界,即使是重尾分布。
Jun, 2024
针对多臂赌博机框架中奖励之间相互关联的情况,我们提出了一种统一的方法来优化这种关联并基于这种情况推广经典赌博算法,其中 C-UCB 是上置信边界算法的相关版本。我们证明了算法的正确性,并通过 MovieLens 和 Goodreads 数据集的实验验证了该算法与经典的赌博算法相比的显著改进。
Nov, 2019
该论文提出了一种新的多臂赌博机框架,在该框架下将 K-armed bandit 问题转化为 C+1-armed 问题。通过利用该框架下的广义上限置信区间算法可以降低算法的遗憾量,以实现一定的算法性能优势。
Aug, 2018
考虑到重复使用某些选项可能是不可取的或不可行的,本文提出了一种新颖的随机多臂赌博机设置,并通过映射到 PINWHEEL 调度问题证明了问题的优化累积奖励不允许有伪多项式时间算法,但它设计了一种贪婪算法和一种基于 UCB 的算法,具有一定的优异性。
Jul, 2019
设计一种不使用奖励分布信息的多臂赌博机算法,通过交替应用贪婪规则与强制探索来实现显著的后悔上界,并提供不同强制探索策略下的问题依赖性后悔上界分析方法,适用于不同奖励分布的固定和分段固定设置。
Dec, 2023