探究了一种带背包的 Bandits 模型,旨在在限制供应 / 预算情况下求解多臂赌博机问题。提出了一种新的算法,采用重复博弈中遗憾最小化的框架,相对于最佳固定动作分布具有 O (log T) 的竞争比率。
Nov, 2018
在这篇论文中,我们提出了一种广义的勘探 - 开发权衡模型,该模型允许在时间序列上对任意凹奖励和凸度约束进行决策,并对时间范围进行规定。我们证明了一种用于 MAB 的 UCB 系列算法自然而简单的扩展,提供了一个具有近乎最优的后悔保证的多项式时间算法,满足 Badanidiyuru 等人给出的 BwK 特殊情况下的边界,这一点非常惊人。此外,我们还通过建立此问题与其他研究领域中好的算法之间的有趣联系,提供了更高效的算法。
Feb, 2014
本文提出了一种适用于多臂赌博机问题的解决方案,只需要以线性时间复杂度存储未知参数,可以处理一般的掌握参数相关性的问题,并用于对网络中的最大权匹配、最短路径及最小生成树计算问题的解决。
Nov, 2010
本文讨论在不确定性的情况下如何在多臂老虎机问题中进行赌博,提出了一种正式的处理方法,并建立了不同类型的奖励变化和最小化遗憾之间的直接联系。
May, 2014
本调查报告主要关注于多臂赌博问题中两个极端情况的分析,即独立同分布回报和对抗性回报,并对有限行为、情境赌博模型等进行了分析。
Apr, 2012
通过建立离散选择模型与在线学习和多臂赌博算法领域之间的联系,本文的两个主要贡献是提供了一类算法的次线性遗憾界,包括 Exp3 算法作为特例,并引入了一类新的对抗多臂赌博算法,借鉴了 Wen (2001) 首次提出的广义嵌套逻辑模型,这些算法能够通过封闭形式的采样分布概率实现高度的模型调优灵活性。为了演示我们算法的实际实施,我们进行了数值实验,重点关注随机赌博的情况。
Oct, 2023
该研究提出了一种 BwK 框架的一般化模型,允许非单调资源利用,并提出了一个灵活的双重模板以处理任何具有再生性问题的在线学习问题,包括对抗和随机输入,同时可用于解决一些实际相关的经济问题。
Jun, 2023
本文研究多臂老虎机问题的遗憾下界,并利用 Kullback-Leibler 分歧的已知特性证明了非相对论、分布依赖的限制。这些限制特别表明,在初始阶段遗憾几乎线性增长,并且在最后阶段仅出现知名的对数增长。证明技术突出了信息理论论证的本质,并去除了所有不必要的复杂性。
Feb, 2016
研究一种新颖的多臂赌博问题,旨在解决公司在探索最大化收益新策略的同时,保持其收益在固定时间内持续增长的挑战。 通过提出自然而又新颖的策略来维护限制,我们在随机和对抗设置下分析了限制维护的代价。
本文研究基于多维随机向量臂收益的赌博机问题,证明了在解决特定问题时使用相应的相位策略可以达到最优的累计遗憾和贝叶斯风险,并提出了针对通用问题的近似最优解。
Dec, 2008