Nov, 2023

线性赌博机的集成抽样：小集成即可

HTML
PDF
TL;DR我们提供了第一个对于随机线性老虎机设置的集成抽样方法的有用、严格的分析，特别是在标准假设下，对于一个交互时域为T的d维度随机线性老虎机，在大小约等于d log T的集成抽样方式下，所产生的后悔从数量级上被界定为(d log T)^(5/2) × sqrt(T)。本文是第一个在任何结构化设置下不要求集成的大小与T线性扩展，同时达到接近sqrt(T)量级后悔的结果。本文也是第一个允许无限动作集的结果。
发现论文，激发创造
  • Thompson采样用于复杂的赌博机问题

    考虑了具有复杂操作的随机多臂赌博问题，其中决策者在每轮中进行复杂操作而不仅仅是基本臂。复杂操作的奖励是基本臂奖励的某些函数，并且观察到的反馈可能不是每个臂的奖励。作者在一般情况下证明了一种频率后悔上限和 Thompson 抽样算法的 相容性，并应用于包括选择臂子集的一类复杂赌博问题中。

    Nov, 2013

  • 线性汤普森抽样再探

    在随机线性赌博机问题中，我们为Thompson采样的后悔证明提供了一种替代证明方法。我们展示了后悔与目标函数的敏感性有关，并且选取与乐观参数相关的最优臂可以控制后悔，在具有固定概率为乐观的采样分布下来看，Thompson采样可以作为一种通用的随机化算法。我们还证明了这个理论可以轻松应用到正则化线性优化和广义线性模型问题中。

    Nov, 2016

  • 稀疏随机赌博机

    本文研究了经典多臂老虎机问题的稀疏情况，并提出了一种算法，其遗憾值与臂数的正比例关系被缩小至仅与正收益臂数相同，同时证明了其最优性。

    Jun, 2017

  • 结构化随机赌臂问题中的最小探索

    介绍了一类广泛的随机赌博问题，其中将臂与相应的奖励映射的函数具有一些已知的结构特性。推导了这些问题的渐近特定情况下的遗憾下界，并且开发了OSSB算法，其遗憾匹配了这个基本极限。通过数值实验展示了OSSB的效率，并且证明OSSB优于包括汤普森取样在内的现有算法。

    Nov, 2017

  • 线性参数赌博机的近似极小极大后悔

    研究了有限动作集的线性上下文强化学习问题，介绍了一种名为VCL SupLinUCB的算法，并表明其与最佳下界相匹配，相较于之前的算法分析，节省了两个对数因子。

    Mar, 2019

  • 渐进最优信息导向采样

    介绍了一种基于信息导向采样（IDS）框架的简单高效的针对动作数有限的随机线性赌博机问题的算法，在有限时间内渐近最优，并且几乎是最坏情况下的最优。研究发现IDS如何在遗憾和信息之间平衡权衡，并揭示了最近被提出的原始对偶方法和IDS算法之间的惊人联系。通过实验表明，IDS在有限时间内与UCB竞争力强，在渐近阶段更优。

    Nov, 2020

  • 多臂赌博和强化学习中的模型选择的遗憾界平衡和消除

    该文章提出了一种简单的模型选择方法，用于解决随机赌博和强化学习问题，并通过平衡算法的候选遗憾边界，以及淘汰违反其候选边界的算法来消除算法，从而证明该方法的总遗憾由最佳候选遗憾边界的一个乘性因子限制。

    Dec, 2020

  • 广义线性赌臂机在参数漂移下的遗憾界

    本文探究了广义线性Bandits在非稳态环境中的应用，比如参数漂移等问题，提出了一种新增添的算法，基于动态问题的推断，解决了广义线性Bandits在非稳态环境下表现出的缺陷，拥有了更优秀的性能表现。通过对于动态问题投影过程的修改，我们设计出了一种具有结构性特点的算法。经过实验证明，我们的算法达到了更好的性能表现。

    Mar, 2021

  • 基于几何意义的线性赌博机算法平衡性能和理论保证

    该论文提出了一种基于数据驱动技术的算法，利用不确定椭球的几何性质追踪算法的习得性能，在不同的问题实例上实现实例相关的频率遗憾边界，从而实现算法实例纠错，并在保留基础算法大部分优良性质的同时，达到最小化讽刺性遗憾代价。

    Jun, 2023

  • 线性强化学习问题的信息论界限和紧凑遗憾率

    该论文研究了贝叶斯后悔和汤普森抽样算法在赌博问题中的变体。它建立在信息论框架的基础上，通过率失真分析提供了关于线性赌博问题的后悔率上界。使用链接论证，我们针对度量动作空间的赌博问题建立了新的界限。在奖励的适当连续性假设下，我们的界限为d维线性赌博问题提供了紧凑的速率。

    Mar, 2024