Bandits 问题的 Pareto 遗憾前沿
研究了一种新型的 K 武装强盗问题,介绍了一种针对这一问题的新算法,并展示了在特定条件下可以实现有限的预期累计遗憾,同时提供了依赖于问题的累计遗憾下限,显示出至少在某些特殊情况下,新算法是近乎最优的。
Nov, 2014
本篇论文旨在应对多臂赌博机问题中存在多个最优 / 近似最优机械臂的后悔最小化问题,通过提出自适应算法来自动适应问题的难度,并在理论和实验方面展现了该算法的优越性。
Jun, 2020
研究了随机多臂赌博问题中期望值和尾部风险之间的权衡,提出了一种新的策略以实现任何遗憾阈值的最优遗憾尾部概率,该策略在最坏情况下和实例相关情况下分别实现了 $\alpha$- 最优和 $\beta$- 一致,探究了最差情况和实例相关情况下的遗憾期望和遗憾尾部风险之间的权衡,同时表明在知道规划时间范围时,尾部风险可以降低。
Apr, 2023
该研究提供了敌对强盗算法必须遭受的遗憾的新的下界,并证明了对于最佳臂的总损失或损失的二次变化的上界是接近紧的。此外,研究还证明了两个不可能的结果,即单臂最优和遗憾不能随损失范围的提高而扩展。相比之下,在完全信息设置中这两个结果是可能的。
May, 2016
研究通过交换信息在底层网络上通信的代理,以优化共同的非随机多臂赌博问题中各自的遗憾。我们推导出遗憾最小化算法,其中保证每个代理 v 的期望遗憾都是(1+K/|N (v)|)^T 的平方根量级。
Jul, 2019
在随机线性赌博机的框架中,我们获得了强化的后悔概念的紧密上界。这个强化的后悔概念被称为 Nash 后悔,它被定义为线性赌博机算法累积的预期奖励的几何平均值与(事先未知的)最优解之间的差异。我们开发了一种算法,在有限的臂集和无限的臂集两种情况下,实现了 Nash 后悔的上界。
Oct, 2023
本文研究多臂老虎机问题的遗憾下界,并利用 Kullback-Leibler 分歧的已知特性证明了非相对论、分布依赖的限制。这些限制特别表明,在初始阶段遗憾几乎线性增长,并且在最后阶段仅出现知名的对数增长。证明技术突出了信息理论论证的本质,并去除了所有不必要的复杂性。
Feb, 2016
本文研究了 K-armed dueling bandit 问题,提出了一种受 Deterministic Minimum Empirical Divergence 算法启发的算法,并得到了匹配下界的后悔上界,实验结果表明该算法明显优于现有算法。
Jun, 2015