May, 2014

Lipschitz Bandits: 遗憾下限和最优算法

PDF
TL;DR研究了随机多臂赌博问题中期望奖励是武器的 Lipschitz 函数的情况，提出了两种算法 OSLB 和 CKL-UCB，并衍生出上限，针对连续武器集合的情况建议首先离散化行动空间再应用算法，同时也考虑到了具有类似性质的背景下文本字形赌博。
stochastic multi-armed banditlipschitz functionregret analysisdiscrete and continuous set of armscontextual bandits
发现论文，激发创造
  • 单模臂：遗憾下限和最优算法

    研究了随机多臂老虎机问题，通过一个单峰函数来表示不完全有序的臂的期望奖励。对于离散和连续臂的情况，分别提出了 OSUB 和 UCB 算法，并得到了渐进的上下界和提高性能的实验结果。

    May, 2014

  • Kullback-Leibler 序贝叶斯算法的优化序列分配上界

    本研究考虑在随机多臂赌博机模型下的最优顺序分配问题，提出了一种基于上置信界计算分数函数的泛指数策略，对一些分布类型进行分析，同时给出了算法失策量的有限时间分析结果。实验证明，此策略在使用一般有界回报时比现有技术有显著改进。

    Oct, 2012

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

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

    Jun, 2020

  • 度量空间中悔恨最小化的尖锐分界

    该研究证明了 Lipschitz 多臂赌博机算法的最小损失不可能同时比有限度的度量空间更低和比某些无限度的度量空间更低，并与在线学习的经典拓扑规则相联系。

    Nov, 2009

  • 加权赌博机或：赌博机如何学习扭曲的非预期价值

    文章研究在多臂老虎机问题中引入代价扭曲的概率分布，提出了一些算法，并证明了这些算法在一定条件下能够达到较好的效果，同时给出了相关的理论分析和数值模拟。

    Nov, 2016

  • 有界随机赌博机及其扩展的 KL-UCB 算法

    本文针对随机赌博问题，提出了一种在线动态索引策略 KL-UCB 算法，并通过有界回报和伯努利回报两个方面的研究证明了其优越性和适用性，同时展示了比较实验结果，在时间短的情况下依然表现良好，且优于其他算法。

    Feb, 2011

  • 随机多臂赌博问题的遗憾下界和拓展上置信界策略

    通过对经典多臂赌博机（Stochastic Multi-Armed Bandit）的研究，探讨了两种不同的准则下存在的遗憾下界。同时，研究了 UCB 等算法的变体，证明了这种情况下不可能设计一种自适应的策略来选择最优算法。

    Dec, 2011

  • Dueling Bandit 问题的遗憾下限和最优算法

    本文研究了 K-armed dueling bandit 问题，提出了一种受 Deterministic Minimum Empirical Divergence 算法启发的算法，并得到了匹配下界的后悔上界，实验结果表明该算法明显优于现有算法。

    Jun, 2015

  • 具有对数或次线性遗憾的约束上下文臂机算法

    本文对具有预算和时间限制的约束情境赌博问题展开了研究，提出了一种高效算法 UCB-ALP 以实现对其进行近似求解并达到对数遗憾。

    Apr, 2015

  • 优化置信区间上界算法：改进有限臂赌博机的遗憾

    提出了一种基于 UCB 并具有适当的置信参数平衡风险和过度乐观代价的随机有限臂老虎机算法，同时具有最优问题依赖性遗憾和最坏情况遗憾。

    Jul, 2015