研究了固定数量的臂之间的序列资源分配问题,提出了一种算法并证明了 O(log n)的后悔上限,同时证明了这个上限是紧密的。该算法优于以前的算法,并且关注的关键是资源分配和成功率。
Mar, 2018
我们在本文中解决了一种带有任务转移的在线网络资源分配问题,提出了基于指数加权方法的随机在线算法,证明了该算法具有次线性时间后悔,通过对人工数据进行性能测试并与强化学习方法进行比较表明我们的方法优于后者。
Nov, 2023
本文研究了一个在线资源预订问题,通过一个由两个计算节点组成的通信网络,在有限时间内最小化整体预订成本,并且保持累计违规与运输成本在一定预算限制下的在线重复博弈,提出了一个在线鞍点算法来解决该问题。
May, 2023
我们探索了一种用于动态公平资源分配问题的主动学习方法,该方法假设在在线资源分配过程的每个时期,仅从选择的代理人子集中获取反馈。尽管存在这种限制,我们提出的算法在包括资源分配问题中常用的公平度量和匹配机制中的稳定性考虑等各种度量中,提供了与时间周期数次线性相关的后悔界限。我们算法的关键洞察在于通过利用对决性的上限和下限置信区间来自适应地识别最具信息量的反馈。通过这种策略,我们证明高效的决策不需要大量的反馈,并为各种问题类别产生高效的结果。
Jun, 2024
本文研究用多臂赌博机问题的方法,解决用户和资源之间的最佳匹配问题,采用马尔科夫链的状态演变,采用匹配学习算法实现。
Dec, 2010
研究了在随机多臂老虎机中探索利用可分配计算资源的问题,提出了两个不同场景的算法,并验证了实验所得结论优于基准算法。
Oct, 2020
本文提出一种针对多个资源分配问题的算法体系,将在线请求建模为每次从未知的概率分布中独立抽取,给出了一个在任意接受数据的情况下获得一定比例最优解的单一算法,并且探究了如何在任意情况下应对敌对分布。同时,文中提出了解决大型 LPs 混合装填覆盖问题的快速算法,并分析了该算法在在线拍卖、网络路由和广告策略方案等特殊情况下的应用。
Mar, 2019
研究在预算分配中使用直接搜索方法,提出了一种改进的算法来加速梯度下降方向的识别,并将算法的累计遗憾度分析为 T 的 2/3 次方的上限。
Oct, 2022
介绍了一种称为带背包的赌徒问题的通用模型,结合了随机整数规划和在线学习的方面。该论文提出了两种算法来解决这个问题,它们的报酬接近于信息论上的最优解,但同时带背包的赌徒问题相比传统的赌徒问题更具挑战性。
May, 2013
考虑到重复使用某些选项可能是不可取的或不可行的,本文提出了一种新颖的随机多臂赌博机设置,并通过映射到 PINWHEEL 调度问题证明了问题的优化累积奖励不允许有伪多项式时间算法,但它设计了一种贪婪算法和一种基于 UCB 的算法,具有一定的优异性。
Jul, 2019