Mar, 2024

LinearAPT：适应性算法用于有固定预算的线性赌奇臂问题

PDF
TL;DR该研究深入研究了阈值线性赌博机（TLB）问题，这是随机多臂赌博（MAB）问题中的一个细分领域，侧重于在资源约束下最大化对线性定义的阈值的决策准确性。我们提出了 LinearAPT 这个新算法，它适用于 TLB 的固定预算情景，为优化序贯决策提供了高效的解决方案。该算法不仅对估计损失提供了理论上界，还展示了在合成和实际数据集上的强大性能。我们的贡献突出了 LinearAPT 的适应性、简洁性和计算效率，使其成为解决复杂序贯决策挑战的重要工具。
thresholding linear bandittlb problemdecision accuracylinearaptsequential decision-making
发现论文，激发创造
  • 最优阈值线性赌臂机

    本研究旨在探讨一种新颖的纯探索问题：在随机线性赌臂问题中具有固定置信度的 ε- 阈值赌臂问题（TBP）。我们证明了采样复杂度的下界，并将一种设计用于解决线性情况下的最佳臂识别问题的算法扩展到了 TBP 问题中，该算法是渐近最优的。

    Feb, 2024

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

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

    Jun, 2020

  • 针对随机线性赌博机的问题复杂度自适应模型选择

    本文旨在解决两个流行的随机线性赌博机问题的模型选择问题，并提出了一种算法来适应未知的问题复杂性，其利用参数范数作为线性赌博机模型选择的标准，以帮助选择正确的模型。

    Jun, 2020

  • 阈值赌博机问题的最优算法

    本文提出一种基于启发式算法的无参数算法，用于解决特定的组合纯探索随机赌博机问题，以寻找一组平均值高于给定阈值的摇臂，满足给定精度和一定的时间限制，并证明该算法是情况下的最优解决方案，并提供了相应的上下界。本文是首个针对纯探索设置的固定预算问题，并构建了最优策略。

    May, 2016

  • 线性约束下的纯探索赌博机问题

    本文提出了两种渐近最优的算法，基于 Track-and-Stop 方法和博弈论方法，用于寻找多臂赌博机环境中具有一定置信度的最优策略，特别考虑了带有线性约束的情况，并探讨了约束难度对问题的影响。

    Jun, 2023

  • 基于阈值的在线主动线性回归

    该研究考虑在线主动学习来收集回归建模的数据，提出了一种基于阈值的算法来选择最具信息量的观测数据，并将其推广到高维稀疏线性回归，仿真结果表明该算法相对于被动随机抽样具有显著优势。

    Feb, 2016

  • 自适应双探索权衡策略用于异常检测

    本文研究一类基于阈值的异常检测问题，提出双重探索算法，通过构建自适应置信区间和自动平衡各臂探索与阈值探索的权衡，实现更高效的异常检测。实验表明本算法在合成和真实数据集上均表现出色。

    May, 2020

  • 线性赌臂机中纯探索的完全自适应算法

    本文提出了第一个完全自适应的算法用于求解线性赌博机中的最优选择问题，并且其采样复杂度与已有算法相当。此外，通过模拟实验表明，在合成和真实数据集上均远优于现有的方法。

    Oct, 2017

  • 线性上下文强化学习模型选择的通用自适应算法

    在上下文强化学习中进行模型选择是一项重要的补充问题。本研究提出了一些新的算法，这些算法可以在数据自适应的情况下进行探索，并提供模型选择保证。

    Nov, 2021

  • 抗对抗攻击的随机线性臂机算法

    研究了随机线性赌博机问题，考虑了对抗攻击，提出了两种 Robust Phased Elimination 算法，证明了在非污染情况下可以获得近似最优的收益，并得出针对这些算法的相对近似最优的加性项。同时，在具有多样化情境的情况下，表明一种简单的贪婪算法是稳健的，近似最优的加性遗憾项，尽管不进行明确的探索并且不知道 C。

    Jul, 2020