本研究探讨了组合多臂赌博的后悔下界,并证明了在所有光滑奖励函数下,这种下界都是合理的,并且根据 Merlis 和 Mannor(2019)提出的 Gini 加权平滑度参数确定单调奖励函数的下界。
Feb, 2020
本文提出了一种适用于多臂赌博机问题的解决方案,只需要以线性时间复杂度存储未知参数,可以处理一般的掌握参数相关性的问题,并用于对网络中的最大权匹配、最短路径及最小生成树计算问题的解决。
Nov, 2010
本文研究了随机和对抗性组合多臂赌博问题。在随机情况下,我们提出了一种特定问题的遗憾下限,并讨论了其与决策空间维数的比例关系。我们提出了 ESCB 算法,该算法能有效地利用问题的结构,并对其遗憾进行了有限时间分析。ESCB 具有比现有算法更好的性能保证,并在实践中显着优于这些算法。在对抗性情况下,我们提出了 CombEXP 算法,其遗憾比比现有最先进算法相同,但对于某些组合问题具有较低的计算复杂度。
Feb, 2015
本文考虑了带障碍的多臂赌博机问题中,包含组合优化的情况下解决局部最优策略的方法。我们扩展了现有模型,使得多个手臂可以按照可行性约束同时进行决策。本文提出了一种自然的贪心算法,并针对其在多种情况下的表现给出了严格的理论保证。
May, 2021
该研究探讨了非静态组合半强盗问题,研究了在动态和切换的情况下,算法所能达到的最佳后悔上限以及需要提前了解的参数,并提供了无需先知参数的算法。
考虑到重复使用某些选项可能是不可取的或不可行的,本文提出了一种新颖的随机多臂赌博机设置,并通过映射到 PINWHEEL 调度问题证明了问题的优化累积奖励不允许有伪多项式时间算法,但它设计了一种贪婪算法和一种基于 UCB 的算法,具有一定的优异性。
Jul, 2019
本研究探讨具有因果关系奖励的分段稳定组合半强盗问题,在我们的非稳态环境中,基本臂的分布变化,奖励之间的因果关系,或者二者同时改变了奖励生成过程。我们提出的算法在复杂环境中具备优越的应用性能。
Jul, 2023
我们设计了一种方差自适应的 OLS-UCB 算法,通过在线估计协方差矩阵的系数,在实践中更容易管理,从而改进了代理方差算法的遗憾上界,并且在满足所有非负协方差系数的情况下,有效利用了半强求职者反馈,在 P≤d 和 P≫d 的指数区间内都表现出良好性能。
Feb, 2024
本文对一类赌博机问题进行了研究,提出了一种新算法,结合非参数统计和传统赌博机算法方法,在最大化累积预期收益的目标下,取得了与理论下界相同的性能,同时具有良好的适应性。
Mar, 2010
研究了多臂赌博问题中的探索和利用问题,并提出了一种基于非均匀采样策略的算法,用于解决带有分段稳定随机赌博问题的情况,并实现了对于超宽带通道选择的模拟测试。
May, 2012