线性上下文多臂赌博机和背包问题
在这篇论文中,我们提出了一种广义的勘探-开发权衡模型,该模型允许在时间序列上对任意凹奖励和凸度约束进行决策,并对时间范围进行规定。我们证明了一种用于MAB的UCB系列算法自然而简单的扩展,提供了一个具有近乎最优的后悔保证的多项式时间算法,满足Badanidiyuru等人给出的BwK特殊情况下的边界,这一点非常惊人。此外,我们还通过建立此问题与其他研究领域中好的算法之间的有趣联系,提供了更高效的算法。
Feb, 2014
研究了具有全局背包限制条件下的上下文多臂赌博问题,提出了一种计算效率更高、后悔更低的算法,复杂度与策略空间的大小成对数关系,并将结果推广到一种没有背包限制但目标是任意Lipschitz凹函数的变体。
Jun, 2015
我们设计了一个算法,能够同时在简单多臂赌博机模式下获得问题相关的最优遗憾率和在线性上下文赌博机模式下获得极小化最优遗憾率,而不需要事先知道哪种模型产生了奖励。
May, 2019
该研究讨论了非参数上下文赌博问题,研究了函数的Hölder类和光滑度参数β之间的插值关系,提出了一种新算法,能够调整到各种光滑度设置,并通过确立匹配的上下限证明其遗憾是速率最优的,从而弥合了现有文献关于参数和非可区分性情境赌徒问题,以及仅使用全局或本地信息的赌徒算法之间的差距,同时也揭示了上下文赌徒问题中的复杂性和遗憾之间关键性的相互影响。
Sep, 2019
本文研究了上下文多样性对随机线性情境赌博机的影响,提出了LinUCB-d算法并分析其遗憾性能,理论结果表明,在多样性上下文的假设下,LinUCB-d的期望累积遗憾被一个常数限制,改善了以往对LinUCB的理解并加强了其性能保证。
Mar, 2020
本文研究了一个约束的上下文线性赌博机问题,提出了一种算法 OPLB 并证明了其 T 轮后悔度的上限,针对多臂赌博机情况提出了高效算法,同时给出了问题的下限和模拟结果。
Jun, 2020
本文研究了具有凹奖励的情境强化学习(CBCR)问题,提出了第一个不限政策空间并能使后悔可控的算法;通过把CBCR算法几何地解释为期望奖励的凸集上的优化算法,有了一种从CBCR后悔到标量奖励强化学习后悔的新方法, 并给出了在排名和公平性限制下CBCR的解法。
Oct, 2022