一种高效的含背包限制多臂赌博算法,以及对凹目标问题的扩展
本文研究了带有资源消耗的线性情境赌博机问题,算法具有近乎最优的遗憾界,并将技术从 Solution 综述中的线性情境赌博机,背包赌博机和在线随机填充问题中结合使用。
Jul, 2015
本文研究了集群上下文强化学习,其中回报和资源消耗是集群特定线性模型的结果,算法无法知晓各个元素的集群成员关系。通过拉动一根臂在一个时间段内会产生回报和对于多个资源的消耗,并且任何资源的总消耗超过约束条件会导致算法终止。因此,最大化总回报需要学习回报、资源消耗和集群成员关系的模型。我们提出了一种算法,在时间段的数量上具有亚线性的遗憾,并且不需要访问所有的臂。特别地,我们证明只需对随机选择的一部分臂执行一次聚类即可达到这个结果。为了实现这个结果,我们结合了计量经济学和约束条件强化学习的文献中的技术。
Aug, 2023
在这篇论文中,我们提出了一种广义的勘探 - 开发权衡模型,该模型允许在时间序列上对任意凹奖励和凸度约束进行决策,并对时间范围进行规定。我们证明了一种用于 MAB 的 UCB 系列算法自然而简单的扩展,提供了一个具有近乎最优的后悔保证的多项式时间算法,满足 Badanidiyuru 等人给出的 BwK 特殊情况下的边界,这一点非常惊人。此外,我们还通过建立此问题与其他研究领域中好的算法之间的有趣联系,提供了更高效的算法。
Feb, 2014
探讨 K-armed bandit 问题下的 noisy reward,提出了一种简单实用的算法(kNN-UCB),并得到了紧密的 top-arm identification 和 sublinear regret 边界,并讨论了该算法的全局 intrisinic dimension 和 ambient dimension 的 regret 边界,同时介绍了对于无限武装情境下 bandit 算法的扩展和实验证明了算法在多种任务上的优越性。
Jan, 2018
本文研究了具有凹奖励的情境强化学习 (CBCR) 问题,提出了第一个不限政策空间并能使后悔可控的算法;通过把 CBCR 算法几何地解释为期望奖励的凸集上的优化算法,有了一种从 CBCR 后悔到标量奖励强化学习后悔的新方法, 并给出了在排名和公平性限制下 CBCR 的解法。
Oct, 2022
研究如何在高维度环境下应用稀疏估计和在线学习算法改进上下文强化学习中的多臂老虎机与背包问题,通过联合在线估计和原始 - 对偶框架,控制背包容量,从而取得了特征维度对数级依赖的次线性遗憾,同时在数据贫瘠和数据丰富情况下实现了最优遗憾结果。
Nov, 2023