AAAIJan, 2018

非参数随机情境臂机

PDF
TL;DR探讨 K-armed bandit 问题下的 noisy reward，提出了一种简单实用的算法（kNN-UCB），并得到了紧密的 top-arm identification 和 sublinear regret 边界，并讨论了该算法的全局 intrisinic dimension 和 ambient dimension 的 regret 边界，同时介绍了对于无限武装情境下 bandit 算法的扩展和实验证明了算法在多种任务上的优越性。
k-armed banditnoisy rewardcontext dimensiontop-arm identificationregret bound
发现论文，激发创造
  • 半参数情境赌博机

    该论文研究了半参数上下文赌博机问题，设计了新的算法来解决非线性混淆影响下的奖励估计问题，并通过实证评估证明了该算法的有效性。

    Mar, 2018

  • 一种新的非平稳情境赌博算法：高效、最优和免参数

    提出了首个无需参数的、高效的、动态遗憾最优的上下文赌博算法，通过引入回放阶段来保持对非平稳的探索，并在探索和开发之间保持良好的平衡。

    Feb, 2019

  • 非平稳环境下高效应对背景干扰的 Bandit 算法

    本研究开发了多种高效的上下文推断算法，为非平稳环境提供了有效的解决方案，具有动态适应分布变化的能力，同时通过对各种标准回归进行分析，证明了在时间和空间成本上都能达到最优的效果。

    Aug, 2017

  • 无悔的神经上下文赌博机

    提出了基于神经网络的算法 (NN-UCB) 来解决序列决策中的上下文强化学习问题，证明了该算法的后悔值可以和使用 NTK-UCB 算法等价。

    Jul, 2021

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

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

    Jun, 2015

  • 上下文阻塞赌博机

    该论文研究了一种新的上下文多臂赌博问题，其中玩家在每个时间步观察独立采样的上下文，以确定每个臂的平均回报，但播放一个臂会在未来的一定时间步内阻止它。作者提出了基于 UCB 的算法来解决这个问题，同时介绍了延迟利用和机会抽样的概念。

    Mar, 2020

  • 具有延迟奖励的上下文多臂赌博机的随机分配与非参数估计

    研究带有协变量的多臂赌博问题，在可能存在奖励延迟的情况下，通过对延迟的概率分布进行一些温和假设，并使用适当的随机选择武器策略，证明了该策略的强一致性。

    Feb, 2019

  • 广义线性情境赌博机的可证明最优算法

    本文提出了针对广义线性情境臂的上界置信度算法，实现了与众不同的性能，同时我们还分析了更简单的上界置信度算法，在特定情况下证明了该算法具有最优的后悔。

    Feb, 2017

  • 基于上置信界探索的神经上下文波段算法

    我们提出了一种新算法 NeuralUCB 来解决随机上下文的赌博机问题，它利用了深度神经网络的表达能力并使用基于神经网络的随机特征映射来构建奖励的上界，证明了该算法能够在一些基准测试中具有实际竞争力且能够保证近乎最优的回报保证。

    Nov, 2019

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

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

    Aug, 2023