本文研究了带有资源消耗的线性情境赌博机问题,算法具有近乎最优的遗憾界,并将技术从 Solution 综述中的线性情境赌博机,背包赌博机和在线随机填充问题中结合使用。
Jul, 2015
本文研究了集群上下文强化学习,其中回报和资源消耗是集群特定线性模型的结果,算法无法知晓各个元素的集群成员关系。通过拉动一根臂在一个时间段内会产生回报和对于多个资源的消耗,并且任何资源的总消耗超过约束条件会导致算法终止。因此,最大化总回报需要学习回报、资源消耗和集群成员关系的模型。我们提出了一种算法,在时间段的数量上具有亚线性的遗憾,并且不需要访问所有的臂。特别地,我们证明只需对随机选择的一部分臂执行一次聚类即可达到这个结果。为了实现这个结果,我们结合了计量经济学和约束条件强化学习的文献中的技术。
Aug, 2023
研究了具有全局背包限制条件下的上下文多臂赌博问题,提出了一种计算效率更高、后悔更低的算法,复杂度与策略空间的大小成对数关系,并将结果推广到一种没有背包限制但目标是任意 Lipschitz 凹函数的变体。
Jun, 2015
本文提出了一种基于投影梯度下降思想的具有公平性约束的上下文赌博问题解决算法,能够处理特定成本约束条件下的收益最大化问题。
May, 2023
探讨 K-armed bandit 问题下的 noisy reward,提出了一种简单实用的算法(kNN-UCB),并得到了紧密的 top-arm identification 和 sublinear regret 边界,并讨论了该算法的全局 intrisinic dimension 和 ambient dimension 的 regret 边界,同时介绍了对于无限武装情境下 bandit 算法的扩展和实验证明了算法在多种任务上的优越性。
Jan, 2018
在这篇论文中,我们提出了一种广义的勘探 - 开发权衡模型,该模型允许在时间序列上对任意凹奖励和凸度约束进行决策,并对时间范围进行规定。我们证明了一种用于 MAB 的 UCB 系列算法自然而简单的扩展,提供了一个具有近乎最优的后悔保证的多项式时间算法,满足 Badanidiyuru 等人给出的 BwK 特殊情况下的边界,这一点非常惊人。此外,我们还通过建立此问题与其他研究领域中好的算法之间的有趣联系,提供了更高效的算法。
Feb, 2014
通过将属于再现核希尔伯特空间的损失函数纳入到对手性线性背景乐队的在线学习问题的研究中,我们提出了一种计算有效的算法,该算法利用一种新的对损失函数进行乐观偏差估计的方法,在对底层内核进行的各种特征值衰减假设下实现接近最佳的后悔保证。
Oct, 2023
介绍了一种称为带背包的赌徒问题的通用模型,结合了随机整数规划和在线学习的方面。该论文提出了两种算法来解决这个问题,它们的报酬接近于信息论上的最优解,但同时带背包的赌徒问题相比传统的赌徒问题更具挑战性。
May, 2013
研究高维稀疏特征的随机线性臂模型中,在数据匮乏的情况下,特征向量遵守固定的探测分布,通过探索然后提交算法,得到了 $Ω(n^{2/3})$ 的无维度极小遗憾下界和 $Θ(n^{2/3})$ 的上界。
Nov, 2020
探究了一种带背包的 Bandits 模型,旨在在限制供应 / 预算情况下求解多臂赌博机问题。提出了一种新的算法,采用重复博弈中遗憾最小化的框架,相对于最佳固定动作分布具有 O (log T) 的竞争比率。
Nov, 2018