May, 2023

使用背包问题的上下文臂局部总成本约束，在公平性中的应用

PDF
TL;DR本文提出了一种基于投影梯度下降思想的具有公平性约束的上下文赌博问题解决算法，能够处理特定成本约束条件下的收益最大化问题。
contextual banditknapsackscost constraintsfairnessprojected-gradient-descent
发现论文，激发创造
  • 一种高效的含背包限制多臂赌博算法，以及对凹目标问题的扩展

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

    Jun, 2015

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

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

    Jul, 2015

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

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

    Nov, 2023

  • 带阶段约束的情境强化学习

    我们在上下文感知强化学习中研究了阶段限制的情况，并提出了一种上界置信区间算法来平衡探索和约束满足，同时证明了其遗憾界。

    Jan, 2024

  • $α$- 公平上下文强化学习

    设计了一种高效算法，确保在全信息和强盗反馈设置中几乎达到次线性的遗憾，以解决 alpha-fair contextual bandits 问题。

    Oct, 2023

  • 学习中的公平性：经典和情境赌博机

    本研究介绍了多臂赌博问题中的公平性概念以及提出了基于 “chained” 置信区间的多臂赌博问题的可证公平算法，并证明了任何公平算法必须具有该算法的时间复杂度，同时也证明了公平和非公平学习之间有强烈的界限。在一般情境中，本研究证明了公平性与 KWIK 学习模型的紧密联系，并提出了一种多项式时间复杂度的可证公平算法来解决线性上下文赌博问题。

    May, 2016

  • 聚类线性情境强化学习与背包

    本文研究了集群上下文强化学习，其中回报和资源消耗是集群特定线性模型的结果，算法无法知晓各个元素的集群成员关系。通过拉动一根臂在一个时间段内会产生回报和对于多个资源的消耗，并且任何资源的总消耗超过约束条件会导致算法终止。因此，最大化总回报需要学习回报、资源消耗和集群成员关系的模型。我们提出了一种算法，在时间段的数量上具有亚线性的遗憾，并且不需要访问所有的臂。特别地，我们证明只需对随机选择的一部分臂执行一次聚类即可达到这个结果。为了实现这个结果，我们结合了计量经济学和约束条件强化学习的文献中的技术。

    Aug, 2023

  • 带线性约束的随机赌博机

    本文研究了一个约束的上下文线性赌博机问题，提出了一种算法 OPLB 并证明了其 T 轮后悔度的上限，针对多臂赌博机情况提出了高效算法，同时给出了问题的下限和模拟结果。

    Jun, 2020

  • 对抗性线性情境赌博机的一阶和二阶边界

    考虑对抗性线性上下文赌博机设置，文中给出了一种新的算法，通过利用与不需要上下文设置的线性赌博机的新联系，利用连续指数权重算法在概率单形上的一个截断版本来获得结果，并证明了其结果优于最坏情况下的后悔，特别的当环境相对温和时，考虑了上下文的密度是对数凹的情况，给出了一种同时优于二阶和一阶损失的方法。

    May, 2023

  • 线性上下文强化学习最佳方案

    该研究探讨了在对抗性破坏下的 K 臂线性上下文赌博问题，并提出了一种在随机和对抗环境下具有理论保证的名为最佳两全（BoBW） RealFTRL 的策略。

    Dec, 2023