Nov, 2018

带背包的对抗性赌博机

PDF
TL;DR探究了一种带背包的 Bandits 模型，旨在在限制供应 / 预算情况下求解多臂赌博机问题。提出了一种新的算法，采用重复博弈中遗憾最小化的框架，相对于最佳固定动作分布具有 O (log T) 的竞争比率。
bandits with knapsacksmulti-armed banditsadversarial banditscompetitive ratioregret minimization
发现论文，激发创造
  • 统一随机和对抗性赌博机与背包问题

    本文研究了在预算限制下的拟背包问题下应用 EXP3.BwK 算法解决对抗性赌徒问题，提出了在线学习方案并给出了相应的后悔界。研究表明，当动作成本与预算大小相当时，可实现的后悔界可能会极差，相比于成本受限的情况。

    Oct, 2018

  • 带背包的赌博机

    介绍了一种称为带背包的赌徒问题的通用模型，结合了随机整数规划和在线学习的方面。该论文提出了两种算法来解决这个问题，它们的报酬接近于信息论上的最优解，但同时带背包的赌徒问题相比传统的赌徒问题更具挑战性。

    May, 2013

  • 带补给背包的强盗问题：两全其美

    该研究提出了一种 BwK 框架的一般化模型，允许非单调资源利用，并提出了一个灵活的双重模板以处理任何具有再生性问题的在线学习问题，包括对抗和随机输入，同时可用于解决一些实际相关的经济问题。

    Jun, 2023

  • 具有凹奖励和凸背包的赌博机

    在这篇论文中，我们提出了一种广义的勘探 - 开发权衡模型，该模型允许在时间序列上对任意凹奖励和凸度约束进行决策，并对时间范围进行规定。我们证明了一种用于 MAB 的 UCB 系列算法自然而简单的扩展，提供了一个具有近乎最优的后悔保证的多项式时间算法，满足 Badanidiyuru 等人给出的 BwK 特殊情况下的边界，这一点非常惊人。此外，我们还通过建立此问题与其他研究领域中好的算法之间的有趣联系，提供了更高效的算法。

    Feb, 2014

  • 无遗憾并不足够！通过自适应遗憾最小化处理具有一般约束的赌博机

    通过要求原始算法和对偶算法是弱自适应的，我们证明了在「背包带劫匪」框架中，能够保证子线性的对违规约束的罚值，并同时在随机和对抗的情况下提供最佳性能，并为具有线性约束的上下文劫匪问题提供了首个无 α- 遗憾的保证。

    May, 2024

  • 高维线性多臂赌博机与背包问题

    研究如何在高维度环境下应用稀疏估计和在线学习算法改进上下文强化学习中的多臂老虎机与背包问题，通过联合在线估计和原始 - 对偶框架，控制背包容量，从而取得了特征维度对数级依赖的次线性遗憾，同时在数据贫瘠和数据丰富情况下实现了最优遗憾结果。

    Nov, 2023

  • 保守型赌徒

    研究一种新颖的多臂赌博问题，旨在解决公司在探索最大化收益新策略的同时，保持其收益在固定时间内持续增长的挑战。 通过提出自然而又新颖的策略来维护限制，我们在随机和对抗设置下分析了限制维护的代价。

    Feb, 2016

  • 线性上下文多臂赌博机和背包问题

    本文研究了带有资源消耗的线性情境赌博机问题，算法具有近乎最优的遗憾界，并将技术从 Solution 综述中的线性情境赌博机，背包赌博机和在线随机填充问题中结合使用。

    Jul, 2015

  • 具有多次游戏和预算限制的多臂赌博机

    研究多臂赌博问题下的多次试验和预算约束的拓展，提出上置信区间和 Exp3 算法的具体实现及其性能分析。

    Nov, 2017

  • 一种高效的含背包限制多臂赌博算法，以及对凹目标问题的扩展

    研究了具有全局背包限制条件下的上下文多臂赌博问题，提出了一种计算效率更高、后悔更低的算法，复杂度与策略空间的大小成对数关系，并将结果推广到一种没有背包限制但目标是任意 Lipschitz 凹函数的变体。

    Jun, 2015